パ研合宿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と気付くのは難しくない。