京セラプログラミングコンテスト2021 E - Patisserie ABC 2 (500)
コンテスト中の考察
$ k番目が値の和がいくつの時に入るか求める
両端から中の方向へ$ _2C_2, _3C_2, \cdotsとなっていそう
最後の中央の要素は余りが入る
1個目の要素の値を順に見ていって、3個の要素の値を確定する
3個の和はそれぞれの和毎の要素数の累積和を二分探索する
2個目の要素の値となり得る最小値と最大値を計算
和から1個目の要素と$ nを引いた値と1の最大値の方が最小値になる
最大値は和から1個目の要素と最小値を引いた値
実際には和毎の要素数の計算が間違っているのでWA
$ n=5とかで壊れる
解説の方法
和毎の要素数はDPで求める
DPの遷移は範囲になっているので累積和を使って計算量を減らす
imos法?
範囲の左端に追加し、右端の右に減らす
全要素分上を行った後、左から累積和のように計算して値を更新する
DPの計算が$ \mathcal{O}(N^2)から$ \mathcal{O}(N)になる