ABC241E - Putting Candies

考え方

$N+1$回以内にループに入る．そこで，次のようにすれば良い．

1. $N+1$回を上限にループして
   
   • ループに入るスタート地点startを（アメの合計個数として）検知する．
   • そのときの周期periodを覚えておく
   • 1周期で増えるアメの個数deltaを覚えておく
2. startを超えるまで，愚直にアメの個数を計算する．
3. さらに，残りの操作回数がperiodで割り切れるようになるまで，愚直にアメの個数を計算する．
4. 最後に，(残りの操作回数) ÷ (周期period) × (1周期の増分delta) を加える．

アメの個数がstartを超えたら，その先はどこを起点にしても周期的になる．そこで，頭で調整して，しっぽを出さないのがコツ．

---

公式解説 では1回のループで全て処理している．
Submission #29830033 - AtCoder Beginner Contest 241（Sponsored by Panasonic）

回答例 (Python)

N, K = map(int, input().split())
A = list(map(int, input().split()))

X = 0
order = [-1] * N
X_memo = [0] * (N + 1)
for i in range(N + 1):
    X += A[X % N]
    X_memo[i] = X
    if order[X % N] > -1:
        period = i - order[X % N]
        X_start =  X % N
        delta = X_memo[i] - X_memo[i - period]
        break
    order[X % N] = i

X = 0
while 0 < K and X % N != X_start:
    X += A[X % N]
    K -= 1

while 0 < K  and K % period != 0:
    X += A[X % N]
    K -= 1

X += (K // period) * delta

print(X)

回答例 (C++)

上のPythonコードをそのままC++化すると上手く行かない．
order, X_memoを配列ではなく連想配列を使うようにするとうまくいく（period, X_start, deltaの計算さえ連想配列を使うように変えておけば，判定は配列でもうまくいく）．おそらく，すごく基本的なことなのだろうけど，原因がわからない．．．

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  int N; ll K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  ll X = 0;
  map<int,int> mi;
  map<int,ll> mx;
  int period, X_start;
  ll delta;
  for (int i = 0; i < N + 1; i++) {
    X += A.at(X % N);
    mx[i] = X;
    if (mi.count(X % N)) {
      period = i - mi[X % N];
      X_start = X % N;
      delta = mx[i] - mx[i - period];
      break;
    }
    mi[X % N] = i;
  }
  X = 0;
  while (0 < K && (X % N != X_start)) {
    X += A.at(X % N);
    K--;
  }
  while (0 < K && (K % period != 0)) {
    X += A.at(X % N);
    K--;
  }
  X += (K / period) * delta;
  cout << X << endl;
  return 0;
}