日記 2021/06/09

11時ごろ目覚める。家に食材がピーマンしかなかったので、近くのスーパーで補給した。13時から演習の授業を受ける。テーマは耐量子暗号、具体的には格子暗号のさわりの話を聞いた。Minkowskiの定理を使った平方剰余の相互法則の証明など、面白い話もあったが、1時間ちょっとでは浅い理解しかできない。一応授業時間は16時までなのだし、もっと長く話してもらいたかった。

演習が終わったので、スーパーへ歩いているときに解けた問題を実装する。

C - 暗闇帰り道 atcoder.jp

解法と感想(クリックで展開)

難しかった。最小値の最大化なので、とりあえず二分探索の判定問題を考える。上下左右に移動できるのに加え、あるマスに至るまでの時間に依存して移動できるマスが変わるので、単純に値を確定していくことができない。「あるマスに早く到着して悪いことはない」という考察から、BFSで解くことができることがわかる。あとは実装するだけなのだが、なんと10WAも出してしまった。ずっと誤差や二分探索の終了条件など、浮動小数点演算に関係するもので落ちているのだと思っていたが、実際は「ゴールに移動できない場合 -1 を出力する」のを忘れていただけだった。浮動小数点の扱いに自信が持てていないため、ミスの原因を特定するのが遅れてしまうことがとても多い。なんとかしたい。


その後、いくつか目についた青diffを解いた。

E - Oversleeping

atcoder.jp

解法と感想(クリックで展開)

これは面白かった。電車と高橋くんは周期的な行動をするので、余りに注目すると、中国剰余定理で解ける形になっていることがわかる。はじめ二分探索のような「アルゴリズム的な」解法を探索してしまい、余りに注目することを思いつくのにかなり時間がかかってしまった。数学ができる人ならすぐ思いつけそう……。


E - Patisserie ABC 2

atcoder.jp

解法と感想(クリックで展開)

実装がものすごく大変だった。 [x^M](x + \cdots + x^n)^3 は疎な多項式 1/(1 - x) の積になるので、累積和で  i,j,k の和が  M になるものの個数を求める。あとは頑張る。多項式・形式的冪級数ライブラリをそろそろ作るべきかもしれないと思っている。ほかの人のコードを見たところ、後半はもっと単純なループで書けたようだ。あとで書き直す。


その後家を出て、池袋のジュンク堂で欲しかった本を購入した。買ったのは

  • 『図書館の大魔術師』5巻×2冊
  • ゆゆ式』10巻
  • 進撃の巨人』34巻
  • 『マツリカ・マハリタ』『マツリカ・マトリョシカ
  • 『なめらかな世界と、その敵』
  • 『本と鍵の季節』

の8冊。『図書館の大魔術師』は本当にすばらしい作品。世界観・絵・キャラ・ワクワク感などがすべてとても高い水準にある。この記事を読んでいる人たちにもぜひ手に取ってもらいたい。

家に帰って食事をしたあと、1問だけ解いた。

B - 花束

atcoder.jp

解法と感想(クリックで展開)

問題じたいはただの線形整数計画問題だが、またしても大量にWAを出してしまった。原因は2つの直線が交わらないケースを完全に失念していたことで、本当にダメ。


青diffのsolvedはこれで225問中101問となった。ついに3桁到達! 6月中に埋めきりたいと思っていたが、少し厳しいかな……。

このあと今日買った本を読みつつ、実験の作業を少しして、寝る。

日記 2021/06/08

およそ10日ぶりの日記である。ここしばらく、大学院入試の出願作業に追われていて、日記を書く心の余裕がなかった。なんとか志望教員を選び、無事に出願を終えることができた。提出から一日経っても「こっちにしておけばよかった」という後悔の念が湧いてこないので、いま考えられる限りでは最善の選択ができたと思う。

さて、今日は朝8時ごろまで演習の課題をやっていた。テーマは機械学習、とくにEMアルゴリズムMCMCで、これまたあまりやる気の起きない分野である。競プロに逃避しつつグダグダと問題を解いていた。やる気が起きないとは言ったものの、「すごい魔法」という程度の認識だった機械学習が、授業や演習を通して、統計学を土台に泥臭くパラメータ推定を頑張る、地に足のついた分野であると実感できた。この例が示すように、応用数学の幅広い分野を基礎から学ぶことができるのは計数工学科の大きな長所であると思っている。

朝ごはんを食べて就寝。14時ごろに起床して授業を受けた。授業を聞きながら青diffの問題を眺めていると、しばらく前に解けなくて放置した問題の解法が一瞬で見えたので実装をした。

E - Second Sum atcoder.jp

解法と感想(クリックで展開)

大きい数字から順に見ていって、すでに数字の入っている場所をsetで管理するだけ。どうして過去の自分はこれが解けなかったんだ? 実装で少し苦労した。解説を見るに、番兵を置いておくとよかったらしい。番兵を置くのは思いつけないことが多いので、意識したい。


途中から授業に集中できなくなってきたので、TopCoderのコーディング環境を整えることにした。ArenaのJava Appletがなぜかダウンロードできなかったり、CLionでなぜかコンパイルが通らなかったり、いろいろと苦労したが、なんとか環境が完成した。今のところSRMに参加する気はないが、SRM Div. 1 Easy Hunting を解こうと思っている。

19時ごろまで暇だったので、少し前に買った『マツリカ・マジョルカ』を読み終えた。マツリカは自分の性癖に刺さるタイプのキャラではなかったが、ストーリーは好き。もう少し主人公の成長後の姿が見たかったという気持ちもあるので、第二巻以降に期待。

郵便受けを見に行くと、Amazonで注文した本が届いていた。ところがいざ開封してみると、新品で注文したにもかかわらず汚れや折れがある。当然すぐに返品手続きをした。Amazonで本を注文するとこういったことが起こりうるとは聞いていたが、いままで自分が被害にあったことはなかったので気にしていなかった。今後は可能な限り店頭で買うことにする。

19時から、学科同期とZoomで話す会に参加した。20時半ごろに解散となったので、夕食を食べたあと、青diffを何問か埋めた。

C - タコヤ木

atcoder.jp

解法と感想(クリックで展開)

 0 以上 M 以下の広義単調増加数列の数」がぱっと出てこなかった。良くない。これがわかればあとはやるだけ。


C - だれじゃ

atcoder.jp

解法と感想(クリックで展開)

やるだけ。setに vectorを持たせたのは初めてかもしれない。


E - Yutori

atcoder.jp

解法と感想(クリックで展開)

初めさっぱりわからなかったが、 C 日以上離れているブロックに分割してみたら、ブロックごとに貪欲でいいことに気がついた。実装がかなり大変だった。実はブロックごとではなく、全体で貪欲をしてしまってよい。解法がわかった瞬間に実装に集中してしまって、その解法を「広げる」方向にまったく意識が向かなかった。反省。


本番で解けなかったABC204-Fをupsolveし、ちょうどいい機会だったので行列ライブラリも作った。あと40分あれば解けたかもしれない。Eで詰まったのが悔やまれる……。

atcoder.jp



青diffのsolvedはこれで225問中96問となった。直近2回のABCで青diffを通すことができていて、青diff埋めの効果を感じている。

日記 2021/05/31

29日と30日の日記は、多忙につき、お休みとなりました。

今日は朝8時ごろまで輪講の予習をしていた。引用されている論文の論理が破綻していて辛い。本番でも一部がお気持ち説明になってしまった。朝食を食べたあと、眠すぎたので12時ごろまで仮眠を取った。

13時から輪講発表。内容は平面的グラフの第2固有値の上界の証明だった。平面的グラフであることを利用して、平面を立体射影で球面上に移すことで、球面の表面積の値で上からの評価を行う、という流れで、内容じたいはかなり面白かった。前半は特に問題なく進んだが、後半は上で述べたとおり微妙な結果に終わってしまった。

輪講が終わったあと、大学に登校して圏論の自主ゼミに出席した。去年の秋に始まったこのゼミでは、hora_algebra が激推ししている "Category Theory in Context" を読んでいる。今回は5章6節の "Limits and colimits in categories of algebras" を途中まで読んだ。群や環については、準同型が同型であることと、準同型が全単射であることが同値であるが、位相空間については全単射だからといって同相とは限らない。ずっと「まあそんなものか」と思っていたこの不一致は、Group や Ring から Set への忘却は monadic であるが、Top から Set への忘却はそうではない、ということから、monadic functor が同型を reflect するという一般的な性質の系として従う。これは個人的にめちゃくちゃ面白かった。最近競プロや課題が忙しくて十分にゼミの予復習ができていないので、今週末に頑張りたい。

家に帰って食事をしたあと、5/30のABC203のD問題をupsolveした。コンテスト中に二分探索は思いついたが、なぜか判定に  O(N^2K^2) かかると思い込んでしまい、この方針を棄却してしまっていた。いざ実装してみるとすぐに書けたので、もったいないことをしてしまったと悔やんでいる。

その後、高校同期とAmong Usをした。今日はインポスター時の勝率が良かったが、相方がうまく立ち回ってくれたことが多かっただけのような……。今回から自動ミュート機能を導入してみた。ミュート忘れがなくなり、会議ごとに墓場チャンネルとメインチャンネルの間を移動する手間も減るなど、いいことずくめだった。

解散後もしばらく雑談をしていて、眠くなったので3時半くらいにDiscordを抜けた。なにか競プロの勉強をしようと思い、2ヶ月ほど前に考えたが解けなかったEDPC-Uを解説ACした。 atcoder.jp atcoder.jp

解法と感想(クリックで展開)

bitDPなのは制約からなんとなく察していたが、状態の持ち方と遷移がよくわかっていなかった。DP配列の定義がよくわからないときは、とりあえず「 i 番目まで見たときの問題の答え」としてみると、そこを起点に考察を進められそう。集合  V の各部分集合  S について、その部分集合  T\subset S を渡るような探索は  O(3^{|V|}) で書ける、ということを学んだ。



考察中の問題の一つがこのテクニックで解ける問題だったので、通しておいた。 atcoder.jp atcoder.jp
解法と感想(クリックで展開)

上のテクニックを知っていれば難しくはない。自分はDP遷移を思いつくのに時間がかかってしまった。現在の頂点集合  S\subset V について、各  T\subset S を「クリーク候補」として調べる、というのがポイント。部分集合がクリークかどうかは事前に計算しておく必要がある。



青diffのsolvedはこれで224問中77問となった。ここ数日忙しくてコンテストに出る以外の精進がほとんどできていない。

明日は補講日かなにかで全休。明日から、情報理工の大学院入試の出願がいよいよ始まる。出願を忘れるわけにはいかないので、志望理由書を書くのを最優先にする。競プロについては、いい加減TDPCを埋めていきたい。

日記 2021/05/28

12時ごろ、起床する。朝ごはんにパスタを茹でて食べる。のんびりしていたら予定出発時刻を過ぎていて、実験に15分くらい遅れてしまった……。

15時ごろに実験が終わったので、学科の控え室に遊びに行く。ぐだぐだと競プロや院試の話をしていた。3年生の間はほぼすべての授業がオンラインで、自分は大学に行ってオンライン授業を受けることもしなかったので、控え室でのこういった交流は4年生に入ってからがほとんどである。

16時すこし前に大学を出て、家に帰る。17時半から数理情報コースのオンライン懇親会に出席した。前半1時間は研究室紹介、後半は研究室ごとのブレイクアウトルームで先生方とお話、というスケジュールだった。先生方からはいろいろな話を聞くことができたが、結局志望する研究室は決まらなかった。ほかの工学部の学科と違って、計数工学科は卒論の配属が10月なので、自分はいまだに研究というものを知らない。期限ぎりぎりまで悩んで、配属された後も隣の芝生を青く見る自分がありありと想像できるが、まあなるようになるだろう。

懇親会じたいが20時に解散となったあと、学科同期数人とZoomに残って雑談をした。皆どの研究室を志望するかで大いに悩んでいた。これまでの中学入試・大学入試・進振りと院試がもっとも違う点として、競う相手の多くが慣れ親しんだ学科同期であることが挙げられる。少ない枠を友人と奪い合うのは本当に辛い。院試までこのストレスが続くかと思うと心が沈むが、自分の経験上一晩寝たら大抵のことは辛くなくなるので、これもそのような一過性のものだと信じたい。

しばらく何も手につかず、ぼんやりとYouTubeを見たり、天鳳で麻雀を打ったりしていた。流石にまずいと思ったので、05/26の日記で述べたとおり、オイラーツアーとLCAの実装をした。ちょうど青diffのなかにLCAを求めるだけの問題があったので、verifyに使わせてもらった。

atcoder.jp atcoder.jp

その後、あまり腰を入れて考察をする気にもなれなかったので、数日前から考えていたが解き方がさっぱり分からなかった2問を解説ACした。

atcoder.jp atcoder.jp

解法と感想(クリックで展開)

上手く範囲を絞って全探索する、という方針でずっと考えていたが、良い構造が全く見えてこなかったので諦めた。想定解は二分探索。全く発想になかった。「 K 番目に小さい値を求めよ」のような問題では二分探索が定石らしい。悔しいが、典型を一つ学べたので良しとする。



atcoder.jp atcoder.jp
解法と感想(クリックで展開)

ACL Beginner Contestの問題なので、遅延セグ木による解法を考えていたが、配列として「\mathrm{mod}\ 998244353 での値」を持とうとすると更新に、「その桁の数字」を持とうとすると総和に、それぞれ  O(N) かかってしまうので途方に暮れていた。結局、そのペア(に近いもの)を持てばよかったらしい。代数系としてなんらかのペア全体の集合を取るのは数学でも頻出なので思いつきたかったが、int とmodint 以外の型を遅延セグ木に乗せる発想が全くなかったし、そもそもそれが可能ということも陽に意識したことはなかったので、仕方ないかな、とも思う。



これで青diffのsolvedは221問中73問となった。

どの研究室を志望するか悩んでいる、ということは、裏を返せば、どの研究室に配属されても楽しめる可能性が高い、ということだ。頼むからどこかには入れてほしい。

日記 2021/05/27

8時ごろ、雨音に叩き起こされた。4時間くらいしか寝ていないので眠い。先日傘をどこかに置き忘れたあと、代替を用意してなかったことを思い出して絶望する。しかたなく近くのコンビニへ濡れながら向かった。傘を買うついでにやよい軒で朝食。350円で健康的な朝ごはんが食べられるのはありがたい。

家に戻ると眠気が鎌首をもたげてきたので、二度寝した。12時ごろに目が覚める。眠かったので布団のなかで競プロの考察をして、解けたので布団から這い出て実装をした。

atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 一見不可能に見えたので制約を見直すと、 A_{ij},B_{ij} がともに小さいことに気がついた。あとはbool値でDPをしてやればよい。余裕で間に合うと思っていたが、実際は959msもかかっていた。


13時ごろに家を出て、秋葉原へ向かう。目的はクールタイムが明けた献血と、1ヶ月前に修理に出したノートパソコンの受け取りだ。献血ルームは平日の昼間にもかかわらず混んでいて、成分献血なのもありかなり時間がかかる。待ち時間に、このルームに来るごとにちびちびと読み進めていた『HELLSING』を読了した。この作品は、自分の「厨二病」と、自分が物語に求めているものにクリティカルに刺さったので、とても気に入った。後者についてはいつか記事にしたい。

献血が終わり、PCを受け取ろうとしたが、受領に必要な控えを家に置いてきてしまった。何をやっているんだろう……。結局、土曜日にもう一度伺うことになった。

その後、昨日に続いて丸ノ内丸善を訪れた。昨日はギフトカードを持ち合わせていなかったので、1冊を購入するにとどめたが、今日は追加で『三体 死神永生』の下巻、『石取りゲームの数学』、『究極の英単語プレミアム Vol. 1』を買った。『石取りゲームの数学』は、競プロでも登場する不偏ゲームにかんする理論を記述した本である。Grundy数を学ぶついでに読んでおきたい。『究極の英単語プレミアム Vol. 1』はいわゆる英単語帳だが、ほかの単語帳で見られない、面白い語彙が多く載っていたので買ってみた。以下にいくつか例を挙げる。

  • 800 pound gorilla 「無視できないもの」
  • arrow in the quiver 「手段の一つ」
  • pizzazz 「活気」
  • take-no-prisoners attitude 「強硬な態度」
  • deep-six 「放棄する」
  • dragoon 「無理やりなにかをさせる」

どれも響きや語源が面白く、頭に残りやすい。自分は地道に単語帳を覚えるという作業が苦手なので、楽しく語彙を増やすことができるこういう本はありがたい。

家に帰り、食事をとる。人参やもやしが余っていたので、昨日にひきつづき野菜炒めを作った。話はそれるが、一人暮らしを始めた当初、その辺のスーパーで適当に購入する食材や日常品の質の悪さに驚くことが多かった。ぱっと思いつくところでは、スーパーの安いハムや、日用品でいうとラップや歯磨き粉など、実家で何気なく使っていたそれらと比べて大きく質が劣る。実家にいたころは気がつかなかった親の気配りをいまさらになって感じる。

21時ごろから、高校同期とAmong Usをした。前半は調子がよかったが、後半インポスターで2敗してしまった。自分がインポスターで負けるときの要因として、序盤に慎重になりすぎて、中盤から終盤で雑なキルをせざるを得なくなって吊られる、というのが多い。もう少しキルに積極的になってもいいかもしれない。

0:30ごろにお開きとなり、そのあと2時間くらい駄弁っていた。最近、友人との話題も就職や院試、研究に関することが多くなってきて、時の経過を感じる。喋りながら青diffの問題を眺めて、解けそうなものを2問解いた。

atcoder.jp

atcoder.jp

解法と感想(クリックで展開) ベルマンフォードを初めて書いた。頂点 1から到達できない、または頂点 Nに到達できない負閉路は考慮に入れないようにする必要がある。自分は前処理としてBFSを各頂点から回し、到達可能性を調べておく方法を取った。正解したあとにGoogleで検索すると、どうやら嘘解法が大量に通ってしまった問題らしい。以下のページの記述が参考になった。
ABC137-E:Coins Respawn ~負閉路検出について~ - 思考の墓場


atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 木の直径を求めるだけ。試験管青diffはこういった問題が多く、典型の復習になる。


青diffのsolvedはこれで221問中70問となった。

明日は昼から実験があるので、12時には起きたい。

日記 2021/05/26

こたつがめに倣って日記をつけることにしてみた。いつまで続くかはわからない。

深夜1時にこの日記を書き始めた。 数理演習の課題が今日までなので、徹夜覚悟で終わらせにかかる。最近ようやく「早めに課題を終わらせる」ことが自分には不可能であるという諦めの境地に至ることができた。 演習の課題はロバスト最適化に関するものだった。いわゆる連続最適化という分野の一分枝である。自分は圧倒的に離散のほうが好みなので、この課題はあまりやる気が起きない。案の定というべきか、今回もとりとめもなくYoutubeを見たりタイムラインを眺めたりと、非効率的な時間の使い方をしてしまった。

眠気に耐えられなくなり、5時ごろに就寝。

12時ごろに起床した。演習の授業を聞きながら、課題の残りを解いてTeX打ちして提出。17時からバイトに出勤し、20時退勤。帰り道に丸ノ内丸善に寄って、『三体』の第三部を買った。このシリーズは、筆者が「理系」の人間であることが筆致からありありと伝わってきて、親近感と安心感を覚える。家に帰ると、昨日注文した『マツリカ・マジョルカ』が届いていた。この筆者の『medium』がとてもよかったので、期待大。

夕食を作る。最近はなんのせいやら、20時以降に外食ができない。バイト終わりに気軽に食事ができなくて本当に困っている。ここ数週間ろくに緑黄色野菜を摂っていなかったので、ニンジンとピーマン、豚肉、もやしを買って野菜炒めにした。味付けは適当だったが、かなりうまくできた。

青diff埋めの続きをする。バイト中に考察した数問を実装した。

atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 見た瞬間に解法が分かった。これは自分の得意分野なので当然だが、自分がコンテスト中に解けなかったABC-Eも、強い人たちから見ると同様に自明なのだろう。実際、ABC-Eは既出の問題ばかりで、精進の最中にも類似の問題によく出会う。早く十分な知識を身につけて、考察勝負のステージに上がりたい。


atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 部分列の和が S になるような添字の集合 \left\{x_1, \ldots, x_k\right\}\ (x_1 \le \cdots \le x_k)それぞれについて、その解への寄与は \ x_1 (n - x_k + 1)と表される。ナップサック問題のDPをベースに、「初めて要素を取ったタイミング」と「和が Sになったタイミング」だけ別に処理し、後者のイベントが起こるたびに解に上のスコアを加算する。自然な発想だけで解けてよかった。

解いたあとにmaspyさんのブログを読んだ。FPSは考察が固まってないころに検討したが、今回は単なる集合ではなく区間なので、よくわからず投げ捨ててしまった。全区間について適当な多項式の積を求めて、足し上げればよい、という発想はなかった。



atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 少し考えるとただの整数計画問題であることがわかる。頑張れば O(1)でも解けそうだが、制約が小さいので全探索をした。例外処理を忘れて2WA。この問題に限らず、ここ2回のARCの敗因が、さほど難しくない問題をバグらせたうえ、雑な提出をして大量のペナをくらったことなので、気をつけたいが……。



atcoder.jp

atcoder.jp

解法と感想(クリックで展開) 普通にシミュレーションすればいい。一回縦/横に反転されたら、その列/行よりも右/下は干渉を受けなくなる。 早く解いている人のコードを見たら、遅延セグ木でぶん殴ってる人が多かった。



青diffのsolvedはこれで221問中67問となった。

オイラーツアーの勉強をすこしした。概念じたいはさほど難しいものではなかったが、できることがかなり多そうで、使いこなすのは慣れが必要だろう。明日はLCAの実装をするつもり。

今日買った『三体』を読む。明日はいろいろとやることがあるので、3時までには寝たい。