A. Permutation Warm-Up
最大値までの偶数が全部作れます.あんまり自明じゃないと思います.
帰納法で示すとして,目標値が小さいなら $p_n=n$,目標値が大きいなら $p_1=n,p_n=1$ としてあげれば示すことができるはず.
B. SUMdamental Decomposition
結構難しい.$n$ が $popcnt(x)$ 以下の場合は自明.そうでない場合には,まず $2^2$ 以上の桁は $1$ 回までしか使わないとしてよいです.よって $1,2$ を使って調整します.場合分けは結構たくさんありましたがサンプルが割と網羅的で助かりました.
C. Neo’s Escape
降順に見て,新しいものが必要ならば新しく置く,ということをします.不要なのは,最寄りの今まで置いたもので処理してもよい場合で,これは最寄りとの間の区間 min をとれば判定できます.
D. Needle in a Numstack
prefix $a$ 項と suffix $b$ 項はそれぞれ周期 $k$ です.
全体も周期 $k$ だと,$n=2k$ のとき以外は答は確定しません.
そうでない場合には,周期 $k$ でない場所があるはずなのでその境界を探します.$\pmod{k}$ での値を固定したとき,先頭と末尾が同じ文字だったらこれは定数列で,そうでなかったら二分探索で境界が発見できます.
ひとつの剰余で境界が求まったら他の境界もその近くにあるはずなので,前後 $k$ 個ずつ程度を探索します.あとはその付近での切断を全部試して,答が何通りあるか確認します.
E. Spruce Dispute
削除と書かれているけど一般的には縮約と呼ばれている操作です.
偶数頂点の場合の最大値は,重心からの距離の和です.ペアをすべて別の subtree からとってくれればよく,重心からの in-order 順に並べて $i$ と $i+n/2$ をペアにするという要領で達成できます.
操作が重心を変えないことがいえて,$1$ 辺を縮約したときのロスは最も浅い葉のところで実現できることも分かります.
$a<b$ などが必要なので注意.
F. Fallen Towers
まず操作ですが,後ろの方の操作は影響しないので,手前から操作をやっていくと再解釈できます.
$i$ 番目では,これまで受け取った石のうちいくつかその場に残すかを選択し,それ以外を右に流すという操作になります.
あとは mex 最大化について考えればよいです.項別に値を減らすのは簡単で,ある石が常に後ろに渡され続けるように操作を変更すればよいからです.なので例えば 0001233 が実現できるならば,0000123 も実現できます.単調増加数列を作ってくださいという制約から,考慮すべきは 0000123 のように suffix に連番があるパターンだけです.
あとは簡単で,二分探索内で冒頭に述べた操作を先頭からシミュレーションすればよいです.