@ を通過したあと . に書き換えた。■C 問題 Illuminate Buildings。難しかった。実装で２つ間違えてペナルティは４回出した。AC が出たのは終了５分前。２乗が通る制約だからと愚直に書いて、念のために最大ケースでテストしたら TLE になりそうだった。愚直というのは始点を固定して全ての間隔を試すというもの。よく考えると右側にある同じ要素を何度も参照するから２乗では済んでいない。そこで間隔を中心に考えることにした。１つおき、２つおき……の各数列について、同じ要素が最長でどれだけ続くかを数える。間隔が S なら長さが N/S 程度になる S 本の数列を考える。間隔の選び方がおよそ N 通りだからこれで O(N^2) になる。ここでも罠があって Array#values_at と Enumerable#chunk と Integer#step を組み合わせた解答が予想よりも時間を食っていた。Enumerable#each_cons には大きい数を引数にしたとき尺取りの計算量 O(N) では済まないらしい罠があると思ってるんだけど、ここにもあったのだろうか。手続き的に書き直して最初に提出するまでに 15 分かけた。そこからペナルティを重ねるんだけど、最後まで見つけられなかったバグは N=1 のケース。間隔に注目したせいで単一要素のケースが漏れて nil を出力していた。■D 問題 Santa Claus 2。どうやって計算量に対処するか悩む。たとえば BIT を使えば各行、各列のどこに家を置いて、どこから家を取り除くかは自在に(対数時間で)できる。あるいは行ごと列ごとに移動区間と家の並びのソート列があれば並行してスキャンしていくことができる。どちらも行データと列データに重複して登録される家を二重にカウントしないために同期が必要。これは行に基づいて得た訪問家リストと列に基づいて得た訪問家リストを最後に線形時間でマージして出力すれば良い。ということを考えてから必要なデータ(行ごと列ごとの移動区間)を集めて整理していった。そうすると家を中心にして考えたとき、行データと列データを参照して二分探索をするとその家が訪問されるかどうかがすぐに判断できるなと気がついて、後半の実装がちょっとだけ楽になった。BIT はいらないし、ソート列の並行スキャンもいらないし、答えのマージもいらない。ランタイムエラーでペナルティを１回出したのは N×N のグリッドを想定していたせい。D の提出をするときに C が WA になっているのに気がついて、C のデバッグをしているときに D が RE になって、C のデバッグを優先したけど結果的にデバッグしやすかったのは D だった。いっときは C をあきらめて E 問題を読んだほど。■E 問題 Snowflake Tree。木 DP かなと思って実装を始めたら親方向の情報が欲しくなって全方位木 DP だと気がついて、残り 10 分での実装をあきらめて C のデバッグに戻った。C は終了５分前に、E は終了 10 分後に AC。最も簡単なタイプの全方位木 DP だと思ったけど、もっと簡単に中心を全探索して間に合う計算量だったらしい。頂点数が N でそこから辿る辺の数が両方向で 2×(N-1) だから間に合う。しかし気付けない。■C のミスと D の重さにやられて E を通す時間がなかったのが悔やまれる。F はどれだけ時間があっても無理なのであきらめがつく。