ABC175 D - Moving Piece (400)
コンテスト中の考察
全パターンを試すのは$ O(NK)で間に合わない
条件から必ずループになっているのでKの内ループ部分はまとめて計算できる
それぞれの点$ iについて、
N回までの移動の内、それぞれの移動回数以下で最大の点数を記録
$ K \le Nなら上の配列でK回移動時の値を出せば良い
ループの長さをチェックし、1ループ内での値の和を出しておく
和が0未満ならループは使わない方が良いのでループ長-1回移動時の値を出せば良い
和がちょうど0なら、0未満の場合の値と0の大きい方を使う
和が0より大きい場合、ループは使える限り使う
Kでループからあふれる数だけ移動時の値を出せば良い
ループ長でKが割り切れる場合はこれが0
WA
コンテスト後の考察
余りが0でも、最後のループを途中で打ち切った場合が良い場合がある
$ [2000, -1000, -100] のような場合、一つ目までで打ち切った方良い
最後1周分だけ一番良い値を使うようにしてAC
N個の要素でそれぞれN回ループを回すので$ O(N^2)