Educational Codeforces Round 151 (Rated for Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 151 (Rated for Div. 2) Dまで。
A x!=1のときを丁寧に場合分け
B 各座標を独立に。
C 部分列DPを使う。https://t.co/NeYvsecE9N
D 前後それぞれからどれだけ大きくできるか見る。ダメだと思いつつ三分探索してWAを出したのは反省。

— titia (@titia_til) June 29, 2023

E. Boxes and Balls

　こたつがめさんの実況放送の振り返りを見てAC。

　コンテスト中、左端の1はどこからどこまで詰められるのだろう？　などと考えていた。大まかな方針はそれで良いのだが、「どこからどこまで」ではなく、全てのnについて試さなくてはいけなかった。

　各i in [0, n)について、何番目のボールをそこに置くか？　そうした場合の移動距離はいくつか？　というDPを考えると三乗のDPになり、それを枝狩りすると通る。

　三乗DP自体は自然なものなので、それは思いつかなくてはいけなかった。