ブログにも解説を載せるのは，2026/08 中くらいにします．ちょっと管理や，自分のための検索資産としていまいちなので．
カテゴリページ → https://maspypy.com/category/codeforces
のお知らせも見てください．
A. Boss Fight
半数より多すぎるやつだけが全部は使い切れません．
B. Always Changing
ケースワーク．
基本的には連長圧縮成分をこわさないようにとっていきます．0, 1 の個数が偏っていなくてこれが行えなくなった時点で，あと数手以内で決着という感じです．
連長圧縮の端の成分についてちょっと場合分けなどします．初手と手数の偶奇を決めると最終的な連長圧縮成分の両端がどうなれるかが限定されて，そこで端の連長圧縮成分を消す判断が必要になります．
あとは細かい計算式を書けばよいですが，愚直を書いたしたくさん修正を繰り返していっぱい実装してしまいました．
C. Risky Tower
2 番目のルールは明らかなので，1 番目のルールを調べるだけでよいです．
座圧セグ木等が面倒だったので，私は二分探索しました．行について降順に調べ，top K sum を priority queue で管理すればよいです．
これは後で気づいたことですが，これにかなり近い実装量，実装方針をとった場合でも，二分探索の log はすぐに外せました．二分探索で check するんじゃなくて，
while (check(K)) {
// データ構造を check(K) 用のものから check(K-1) 用のものに更新
--K;
}のように decremental に check すればよかったです．個人的に忘れがち．
D. Array Replacement
階差数列に置き換えると，操作は隣接要素のスワップということになります．
parity が同じ要素をスワップできるので，成分ごとにソートするのが最適です．
E. Generational Triplets
必要な情報を全部持って，桁 dp をすればよいです．
制約は
- $S[0]\leq a$
- $a+S[1]\leq b$
- $b+S[2]\leq c$
- $c\leq S[3]$
- $2b-a-c=S[4]$
のように書けて，下から桁 dp すれば，状態 $S$ は $O(\log N)$ 通りに抑えられます（$S[3]$ 以外が $O(1)$ 通り）．
F. Spectral Components
色ごとに，木を圧縮して解けばよいです．steiner tree の外に使う点は内側に寄せるか消してもよいからです．したがって，
- $N$ 頂点の木
- $M$ 個の頂点に印あり
- 辺の長さがある（内部に圧縮前頂点だった点がある）
という状況で $O(N)$ 程度の計算量で解けばよいということになります．
重心といえば，印を重みと思ったやつとします．複数あるかもしれませんがひとつとります．重心で根付き木にします．重心を考えてみたのはなぜかというと， $K=1$ の場合どうなるかから思いつきました．
目標集合は，重心を含むとしてよいです．重心から見てある部分木に含まれていたとして，重心側にひとつ引き寄せるタイプの操作を考えると示せるはず．
すると，目標集合は次の操作列によって作れます．
- 重心だけからなる集合で初期化
- いままで作った成分に隣接する頂点を採用（頂点とは，辺の内部頂点も使用可能）
重心だけを選んだ時のスコアを基準にすると，ある頂点を採用した時点で「subtree 内にある印の個数」だけの利得が発生します．
ここでさらに，「いままで作った成分に隣接する頂点」という制約を取り払って単に「subtree 内にある印の個数」が大きいものから採用していきましょう．これで ok です．ある頂点の利得は先祖の利得以下だからです．あとはこの貪欲を実装すればよいです．
