titiaのノート: Educational Codeforces Round 110 (Rated for Div. 2)

2021年6月5日土曜日

　数分遅刻してDまで四完。今回のえでゅふぉC～Eは教育的な出題だったと思う。Cは尺取り法の、Dはセグ木の、Eはダブリングの、本質的な理解を問うている感じがします。

　普段のえでゅふぉは、educationalという名前の割に教育的とは思えない問題が多い気がするけど、今回は良かった。

C. Unstable String

　尺取り法で良いのだが、左端を動かすときの条件がやや書きにくい。

　dequeを使うと尺取り法を書きやすい、というのを目にしていたのを思い出し、この問題で試してみたのだけど、「左端の条件の書きにくさ」はこの方法では緩和されず、時間がかかってしまった。

　でも、普通に（whileとかで）書くよりはちょっと楽だったかも？

　図の通り、セグメント木みたいなことをするのだけど、普段多くの人が書いているセグメント木とは添え字の順番が違うことに注意。

　そこを補正するため、普段の順番と今回の順番で、添え字の対応表を作れば良い。

　私は、対応表を作るときのfor文の範囲を間違えて、対応表に-1を残してしまったためTLEが出てしまった。原因特定に苦労した。

　コンテスト中は、$C_i>C_{p_i}$を見落としていたのでどうしようもなかったが、この条件をちゃんと理解すれば、一番祖先から貪欲にとっていけば良い。

　なら、ダブリングするのかな、というのは思いつく。

　ということは、金がなくなっていない祖先のノードを見つけて、そこから自分の方へ降りていけば良いのだけど、降りるときどうすれば良いの？　というところで詰まった。

　落ち着いて計算量解析をすれば分かりますね。

　なお、実装したけどPyPyだとTLEだったのでKotlinでACしました。ただ、今見ると何人かPyPyで通していますね。