11時ごろ目覚める。家に食材がピーマンしかなかったので、近くのスーパーで補給した。13時から演習の授業を受ける。テーマは耐量子暗号、具体的には格子暗号のさわりの話を聞いた。Minkowskiの定理を使った平方剰余の相互法則の証明など、面白い話もあったが、1時間ちょっとでは浅い理解しかできない。一応授業時間は16時までなのだし、もっと長く話してもらいたかった。 演習が終わったので、スーパーへ歩いているときに解けた問題を実装する。
C - 暗闇帰り道
atcoder.jp
解法と感想（クリックで展開）
難しかった。最小値の最大化なので、とりあえず二分探索の判定問題を考える。上下左右に移動できるのに加え、あるマスに至るまでの時間に依存して移動できるマスが変わるので、単純に値を確定していくことができない。「あるマスに早く到着して悪いことはない」という考察から、BFSで解くことができることがわかる。あとは実装するだけなのだが、なんと10WAも出してしまった。ずっと誤差や二分探索の終了条件など、浮動小数点演算に関係するもので落ちているのだと思っていたが、実際は「ゴールに移動できない場合 を出力する」のを忘れていただけだった。浮動小数点の扱いに自信が持てていないため、ミスの原因を特定するのが遅れてしまうことがとても多い。なんとかしたい。
その後、いくつか目についた青diffを解いた。
解法と感想（クリックで展開）
これは面白かった。電車と高橋くんは周期的な行動をするので、余りに注目すると、中国剰余定理で解ける形になっていることがわかる。はじめ二分探索のような「アルゴリズム的な」解法を探索してしまい、余りに注目することを思いつくのにかなり時間がかかってしまった。数学ができる人ならすぐ思いつけそう……。
atcoder.jp
解法と感想（クリックで展開）
実装がものすごく大変だった。 は疎な多項式と
の積になるので、累積和で
の和が
になるものの個数を求める。あとは頑張る。多項式・形式的冪級数ライブラリをそろそろ作るべきかもしれないと思っている。ほかの人のコードを見たところ、後半はもっと単純なループで書けたようだ。あとで書き直す。
その後家を出て、池袋のジュンク堂で欲しかった本を購入した。買ったのは
の8冊。『図書館の大魔術師』は本当にすばらしい作品。世界観・絵・キャラ・ワクワク感などがすべてとても高い水準にある。この記事を読んでいる人たちにもぜひ手に取ってもらいたい。 家に帰って食事をしたあと、1問だけ解いた。
解法と感想（クリックで展開）
問題じたいはただの線形整数計画問題だが、またしても大量にWAを出してしまった。原因は2つの直線が交わらないケースを完全に失念していたことで、本当にダメ。 青diffのsolvedはこれで225問中101問となった。ついに3桁到達！ 6月中に埋めきりたいと思っていたが、少し厳しいかな……。 このあと今日買った本を読みつつ、実験の作業を少しして、寝る。
