ABC175D
ABC175D
https://gyazo.com/d6e26e7f39e5bc1e3744dfaed3a30560
Kが10^9なのでO(K)も厳しそう
ある始点から1歩進んだ時の終点と得点が与えられている
n歩進んだ時の終点と得点が与えられれば、2n歩進んだ時の終点と得点は容易に求められる
30 * N 回ぐらいの計算で2^1歩から2^30歩まで計算しておけば、2^31未満のKについてO(log K)で得点計算できる
この問題、「K回後の得点」ではなく「K回以下の得点の最大値」だった
残り時間わずかになってから「これループ検出じゃん」と気づいたが間に合わず、3分過ぎて提出したがWAとTLE 原因
負のループ内では最大スコアが負になり得る
なのに初期値を0にしてた
最大スコアを計算するためのmaxが一つループの内側に入ってた(TLE)
正のループがKでちょうど回り切る場合、あまりは0だが、実際には最後の一周を回り切らない方がスコアが高くなる可能性がある
負のスコアがあるならそこを避けた方が良い
下記の公式解説はFalse
このサイクルの「余り」の部分を全て試すことにすると、サイクルの和が正のときは使えるだけ使って、そうでないときは全く使わないのが最適です。