Codeforces Round 1099 (Div. 2)

　ACの二完で過去最悪順位。青に落ちて呆然自失。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1099 (Div. 2) AC二完。過去最悪の順位なんですが。
A 1 3 5 7...
B 分からず。
C min(A)<=2のときは、1や2への回数の小さい方。そうでないときは、どこで合流させれば良いか定まる。
D dfsで決定できる値を決定した後、nの小さい方から適当に決めて良いと思ったがWA。

— titia (@titia_til) May 21, 2026

B. Another Sorting Problem

　破滅した原因の問題。

　（多少解説を見たけど理解できなかったので）大体自力でAC。

　まず、i<jでA[i]>A[j]なら、iには足さず、jには足さない、しかあり得ないと気付かなくてはいけない。

　ここで、足すものと足さないものを分けて考える。

　足す方、足さない方それぞれは広義単調増加でないと条件を満たさない。

　index iが足す方だとしたとき、それ以降のことを考えると足す値はできるだけ小さい方が良い。それは、それ以前のmax-自分の値である。

　この最大値をkとして良い。

　kが決まれば、具体的に、A[i-1]>A[i]であるようなiについて、A[i]+=kする、というのを左からしていき、それで広義単調増加になるかチェックすれば良い。

　コンテスト中は、kを決めてからもう一回……というようなやり方が見えず、for文一回でどうにかなる気がして嵌ってしまった。

　ただ、解法自体は簡単だが、正当性の証明とか、直感的に理解するのは結構難しい気もする。

D. Maximum Prefix Sums

　自力AC。

　解法はあっていた。十分性をチェックしたらACできた。

　dfsするとき十分性をチェックしていたつもりだったが、漏れていたのね。