ABC175D

Kが10^9なのでO(K)も厳しそう
- 繰り返し二乗法でO(log 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
    - このサイクルの「余り」の部分を全て試すことにすると、サイクルの和が正のときは使えるだけ使って、そうでないときは全く使わないのが最適です。
AC

🪴 Quartz 4.0