コンテスト後のツイート
C2 index iについて、j<iなるA[j]はプラス、A[i]はマイナス、j>iはそのまま、としたときの最大値
— titia (@titia_til) May 23, 2026
D 答えで二分探索。混乱したけど、答えより小さいものを、答え以上のものより少なくしたい。
E 二乗なら解けるけど高速化できない。遷移先が区間になったりしないか、とかもらうDPなら、とか考えていた。
E. Deconstruction Tree
解法ツイートなど参照してAC。
コンテスト中に配るDPでのDPは書けていて、それをどう高速化するのかが分からなかった。ツイートで書いたことがあっていて、もらうDPにするともらう先が区間になり高速化可能だった。なんで正しいことを考察しているのに、答えに至れないのか……。
ただ、その上で、答えが何か？ というところでもう一考察必要だった。頂点Nに対して、DPがどこから遷移するか？ というのをちゃんと考えなければならない。それが上手くいかず、結局コンテスト中に書いたDPとランダムテストでチェックしてACした。
惜しくなかったわけではないんだけど、実際にACするには遠かった気もする。