日記　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|})$ で書ける、ということを学んだ。