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するには遠かった気もする。