AtCoder Beginner Contest 423

　ABCDFの五完。Eが解けずレートを落とす。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 423 ABCDFで終了。Eが解けなかった。
A 全探索
B 左右の0の個数を見る。
C 左端の0と右端の0を見つけた後、丁寧に場合分け。
D heapqを使って時間が早い順に処理
E https://t.co/ljzyNkMNNH を見て解けると思ったが答えが合わず。
F https://t.co/ZCg63EjQaY　を見て解いた。

— titia (@titia_til) September 14, 2025

E - Sum of Subarrays

　苦労したがコンテスト中の方針でAC。

　この記事では全ての連続する部分和の総和を求めているので、累積和の差全ての和が答えになっている。

　では、この問題のように、連続部分列に対して考えた場合どうなるか？

　最初に累積和を取っているため、（累積和をSとすると）S[l:r]について同じように値を求めたあと差分を計算する必要がある。

　……と考えていたが、これはダメな方針だった。

　累積和の最初が0になっている代わりに、S[l-1]があると考えれば良い。

　そうすると同じ方針ですっきり書ける。

　これに気付くのに何時間もかかってしまい、ダメでした。

　各A[i]の寄与を考えるという方針も思いついたはずだけど、公式解説のような感じにはできなかった。そもそも立式できていない……。