パ研合宿2021 第2日「SpeedRun」

　A~HとJで九完。

コンテストへのリンク

コンテスト後のツイート

パ研合宿2021　第2日「SpeedRun」A~HとJをAC。その後Kを解けず終了。
E 直前二つと違う数字を使う
F 実験したら(1,N,1,N-1,1,N-2)と言われた
G bit DP
H 各条件について、最小・最大のNを二分探索
J A_iより小さい/一致/より大きいで分けてDP
K 木のトポロジカルソートの個数の数え上げになったが……

— titia (@titia_til) March 28, 2022

J - Min-Max Sequence

　解説AC。

　連結でさえあればどのようなxとyに対しても、「他を変えずに、xとyを入れ替える」という操作が可能だと気付けるかがポイント。単純に行って帰って……と交換したら良さそうだが、自己ループなどがあると壊れるのが難しい。

K - Bracket Inserting 

　括弧列は根付き木と捉えることができる！

　それさえ知っていれば、木DPと気付くのは難しくない。

L - ジグザグ道

　辺を基準にしたダイクストラ法でAC。

　実装が面倒だけど、やること自体は難しくない。

M - Deque and Inversions

　解説AC。実験したが何も思いつけなかった。

　どういうときに値が増えるか？　期待値は？　といったあたりを考えるべきだったか。

N - Polynomial Comparison

　解説AC。

　kのx乗を考える→k進数で考える、というのは自然な発想。

　自力で解けなくちゃいけない問題でした。スピードランでなかったらもっと解かれているはず。

O - Golf

　解説AC。

　Suffix arrayやLCP配列を知っていれば簡単かと思いきや、全然そんなことはなかった。

　解説をちょっと見て、Suffix arrayを使うということをヒントに自力で解こうとしたが撃沈。クエリ先読み＆平面走査が必要とは気付けなかった。

　確かに典型度は高いが、考える要素もあるし、実装も大変だった。