JOI 難易度 12

JOI 難易度 12 の解説を読み漁って感じたことを適当に列挙します。(ネタバレを多々含みます。)

Copy and Paste - 平衡二分探索木だなあという気持ちになった。1 回は書いておいてもいいかもしれないが、逆に平衡二分探索木を書けることもデメリットになり得るのでどうしようかな。

Cake - 最大値/最小値に注目する典型(問題文で見ているのは最大値の方だが考察で必要なのは最小値)ですんなり解けるらしい

計算量解析パートが面白かった。Cartesian Tree 上で色々する問題は経験値が少ないな...

Spaceships - 動的 LCA なので euler tour を動的に平衡二分探索木で管理、こういう問題は現代では出ないかな...

切り取り線 - 自明なノードについては何も考えないだけで上手く行くんだなあという気持ち。解説で言及されている Euler の定理は初めて知ったので面白かった。その後の連結成分の個数を求めるパートも面白かった。区間加算区間総和の遅延セグ木等でも同じようなことがされるが、一般的に 2 種類のクエリがあるとき片方のクエリの区間が全体に対してなら高速に解ける場合このような高速化が可能ということだろうか？(遅延セグ木の更なる抽象化という感覚がある。)

Kanji Shiritori - 普通の communication という感じがする。最後のタイプの回数削減はあまり見たことがなかった気がする。

AAQQZ - 文字列系問題は慣れていなくて苦しく感じる。解説を見るとやることはそこまで難しくなく見えるが、そもそもこのような場合分けに辿り着くことや辿り着いてからの方針選択等が難しいタイプの問題に思える。

Walls - 始め見たときはこれが解けるのか？という気持ちになったがこれも最小値に注目するとかなり上手く議論が回り、最小値や最大値に注目するのは大事なんだなと改めて実感した。

Sparklers - 本当に何もわからなかった。解説を開けてからも常に着火しているのは 1 本という証明がなかなか理解できずに苦しんだ。理解できた今でも狐につままれた感じがする。帰着後の問題の高速化も難しそうな見た目をしているが素直な貪欲を左右からやればいいのがあまりにも簡素で驚き...