Codeforces Round 890 (Div. 2) supported by Constructor Institute

　A, B, E1の三完。Cが解けなかった！

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 890 (Div. 2) supported by Constructor Institute Cが解けない……。
B 1を2に、他を1にした和がsum(A)以下ならOK。
C プラスする区間[i,j]を固定して、A[i]をどれだけ大きく出来るか二分探索したつもりだけどWA。
E1 各頂点について、子供たちを大体半分ずつに分ける。部分和問題。

— titia (@titia_til) August 5, 2023

C. To Become Max

　解説AC。

　最初、二乗が通らない制約だと勘違いしていて、途中で二乗が通ると気付き、足す区間[l, r]の全探索を考えていた。

　が、これは筋が悪い。累積和との差分を使ったりすればコストが求まる気がしていたが、途中で膨らんだりした部分があるとコスト計算が正しくなくなる。このことにコンテスト中は気付いていなかった。

　あるindexをmまで上げるのに必要なコストは？　と考えて、このmを二分探索で解くのが正しい解法だった。これもそれぞれO(n)かかるので、二乗＋二分探索のlogで解ける。