titiaのノート: エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

2022年6月13日月曜日

　ABDEの四完で終了。Fは解きたかった。

コンテスト後のツイート

D イベントソート
E 偶数番目と奇数番目に分けてCounter
F xがIでy番目に出現するとすると、Iでy-1番目までのが左側子孫、y+1番目以降が右側子孫。なことは分かったが、計算量を落せなかった。
— titia (@titia_til) June 11, 2022

C - ±1 Operation 1

　コンテスト後、愚直解を書いて比較してAC。

　解法はツイートした方法で良かったが、Dが負の場合にもx%Dみたいな計算をしていたためWA。その部分をx%abs(D)に直したら通った。

　コンテスト中にコードを読み返して気付かないのはまあ仕方ない。ABCのCで愚直解を書くのはちょっとという気持ちになり後の問題へ行ったのも変なことではないと思う。まあ、あまり気にせずに。

　解説は読んだけど実装方法が今一つ分からず、自分の方法でAC。

　「通りがけ順（in-order）」というのは知らなかったけど、二分探索木とセットで理解しておくべき概念だったようです。

　ツイートに書いたように、

・頂点xがIでk番目に出現するとすると、Iでk-1番目までに出現する頂点が左側子孫、k+1番目以降に出現する頂点が右側子孫

　である。

　この境界はPにおいても境界になっており、その境目の直後の頂点が（存在すれば）xの右側の子になる。（左側の子は、Pにおいて次の点）

　なので、Pでこの境目のindexが何になるかが分かれば再帰で書けるが、コンテスト中はこの境目を求める方法が思いつかなかった。が、冷静になれば、これは二分探索で求められますね。

　解説ではO(N)でやっているようなのだけど理解できていません。

　自力AC。

　座標圧縮が本質の問題。

　Grundy数は基本的には1ずつ増える。ただし、問題文中の禁じ手に該当する個数の山があった場合は、定義通りにGrundy数を求れば良い。

　その際、今までに出現したGrundy数のうち、二回以上登場したものについて何回ずつ登場したかを覚えておくと、計算時間も間に合う。基本的には各数字は一回ずつ登場するので、二回以上登場するものは多くない（高々M回である）。

　解説の遅延セグメント木の解法でAC。

　座標圧縮して遅延セグメント木を使えば良い、と言われればすぐ解けなきゃいけないのに、解説を読んでもなかなか理解できなかったのは反省。

　セグメント木の各ノードに「対応する区間ですでに収穫された実の個数」を持つ、ということをベースに考えれば、LAZY配列には「最後に収穫が行われた日付」を入れておくことで更新が可能になる、と分かりました。