Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2)

　Dまで四完。E解きたかったね。

コンテストへのリンク

コンテスト後のツイート

C2 index iについて、j<iなるA[j]はプラス、A[i]はマイナス、j>iはそのまま、としたときの最大値
D 答えで二分探索。混乱したけど、答えより小さいものを、答え以上のものより少なくしたい。
E 二乗なら解けるけど高速化できない。遷移先が区間になったりしないか、とかもらうDPなら、とか考えていた。

— titia (@titia_til) May 23, 2026

E. Deconstruction Tree

　解法ツイートなど参照してAC。

　コンテスト中に配るDPでのDPは書けていて、それをどう高速化するのかが分からなかった。ツイートで書いたことがあっていて、もらうDPにするともらう先が区間になり高速化可能だった。なんで正しいことを考察しているのに、答えに至れないのか……。

　ただ、その上で、答えが何か？　というところでもう一考察必要だった。頂点Nに対して、DPがどこから遷移するか？　というのをちゃんと考えなければならない。それが上手くいかず、結局コンテスト中に書いたDPとランダムテストでチェックしてACした。

　惜しくなかったわけではないんだけど、実際にACするには遠かった気もする。

F. Load Unbalancing

　解説AC。

・一番大きい数を最後に加えるとして良い

・他のものたちについて、k個に詰めたときのminを最大化したい。

・これは答えを二分探索し、bit DPすれば良い。なぜなら、minの最大化の場合、できるだけ平均的に詰めれば良いので、問題文で指定されたような詰め方を考えなくて良いから。上手く詰める方法があれば、問題文で指定した方法で詰められるので、（二分探索の）mid以上のものが何個あり、最後の箱に何個入っているか？　だけ見ればOK。

　言われてみれば理解できるし、制約にbit DPを使う（だろう）というヒントもある。