この解説はユーザー解説です。

AtCoder 公式が提供する解説を見たい方は、公式解説 をご覧ください。

---

ステップ 1｜具体例で試してみよう（Part 1）

競技プログラミングでは、具体例をヒントにすることで解法が導ける ことがあります。そこで、次のような入力例における答えがどうなるかを計算してみましょう。

\(N = 10\)、\(K = 40\)

\(A = (1, 1, 2, 2, 3, 3, 4, 4, 5, 5)\)

少し面倒ですが、1 回ずつシミュレーションしていけば答えが分かります。\(K = 40\) 回の操作を終えた後のアメの数は \(97\) 個です。

---

ステップ 2｜具体例で試してみよう（Part 2）

次に、ステップ 1 の結果を分析してみましょう。察しの良い人は気づいたかもしれませんが、「追加されるアメの数は \(1 \to 2 \to 3 \to 4 \to 1 \to 2 \to 3 \to 4 \to \cdots\) と変化する」「\(4\) 回の操作でアメが \(10\) 個増える」といった周期性が成り立ちます。つまり、\(1\) 回目の操作を終えた後のアメの数は \(1\) 個でしたが、

• \(5\) 回目では \(11\) 個
• \(9\) 回目では \(21\) 個
• \(13\) 回目では \(31\) 個
• \(17\) 回目では \(41\) 個

といったように規則的にアメが追加されていきます。このような性質を使うと、次のように比較的簡単な計算で答えを求めることができます。

• ギリギリまで高速に計算するため、\(\lfloor (40 - 5) \div 4 \rfloor = 8\) 周期分を追加して考える。
• このとき、\(5 + 8 \times 4 = 37\) 回目では \(11 + 8 \times 10 = 91\) 個のアメがある。
• あとは直接シミュレーションすれば良い。
• \(38\) 回目には \(1\) 個追加されるので、\(91 + 1 = 92\) 個。
• \(39\) 回目には \(2\) 個追加されるので、\(92 + 2 = 94\) 個。
• \(40\) 回目には \(3\) 個追加されるので、\(94 + 3 = 97\) 個。

なお、この方法を使うと、\(K\) が 1 億などの非常に大きい数でも一瞬で答えを計算することができます（興味のある人はやってみてください）。

---

ステップ 3｜規則性の条件を考えよう

それでは、（具体例ではなく）一般のケースにおいて、規則性が成り立つ条件を考えてみましょう。結論から記すと、次のようになります。

次の \(2\) つの値が同じである場合、\(u_1\) 回目以降は \(u_2 - u_1\) 回周期でアメが追加されていく。

• \(u_1\) 回目の操作を終えた後のアメの数 \(\mod N\)
• \(u_2\) 回目の操作を終えた後のアメの数 \(\mod N\)

ステップ 1 の例では \((u_1, u_2) = (1, 5)\) である（下図参照）。実際、アメは \(5-1=4\) 回周期で追加がされていく。

証明は難しいですが、「\(u_1+1\) 回目と \(u_2+1\) 回目に追加されるアメの数は同じ」「したがって \(u_1+2\) 回目と \(u_2+2\) 回目に追加されるアメの数は同じ」「したがって \(u_1+3\) 回目と \(u_2+3\) 回目に追加されるアメの数は同じ」といったように帰納的に考えていくと上手くいきます。

なお、鳩ノ巣原理 より、すべてのケースにおいて \(u_1, u_2 \leq N\) となるような組 \((u_1, u_2)\) が存在することが証明できます（ヒント：非負整数 \(\bmod N\) として取り得る値は \(0, 1, 2, \cdots, N-1\) の \(N\) 通りしかない）。

---

ステップ 4｜解法のまとめ

したがって、次のような手順によって問題を解くことができます。

手順1　前述の \((u_1, u_2)\) を見つける。

手順2　規則性にしたがって、ギリギリのところまでを求める。（ステップ 1 の例の場合 37 回目まで）

手順3　端数の部分は直接シミュレーションすれば良い。（ステップ 1 の例の場合 38～40 回目）

---

ステップ 5｜実装してみよう

最後に実装方法について解説します。まずは 手順1 ですが、\(u_1, u_2\) の値を見つけるため、次のような配列を定義しましょう。

• LastTime[i]：「アメの数を \(N\) で割った余り」が \(i\) であるとき、何回目の操作か
• LastCand[i]：「アメの数を \(N\) で割った余り」が \(i\) であるとき、アメの数は何個か

この配列は、シミュレーションが進むごとに更新されていきます。たとえばステップ 1 の具体例では次のようになります。

• 1 回目の操作ではアメが 1 個になるので、LastTime[1] = 1、LastCand[1] = 1 に更新
• 2 回目の操作ではアメが 2 個になるので、LastTime[2] = 2、LastCand[2] = 2 に更新
• 3 回目の操作ではアメが 4 個になるので、LastTime[4] = 3、LastCand[4] = 4 に更新
• 4 回目の操作ではアメが 7 個になるので、LastTime[7] = 4、LastCand[7] = 7 に更新

そこで、配列の今見ている要素 LastTime[現在のアメの数 % N] が既に書き込まれた値であれば、周期性が見つかったことになります。

たとえば、ステップ 1 の 5 回目ではアメの数が 11 個になりますが、LastTime[11 % 10] = LastTime[1] = 1 であるため \((u_1, u_2) = (1, 5)\) が見つかりました。また、LastTime[1] = 1 であることから、1 回の周期で追加されるアメの数は 11-1=10 個であることが分かります。

これで手順 1 は終わりです。手順2・手順3 については、ステップ 2 でやった通りの計算を実装すれば良いです。C++ でのサンプルコードは次のようになります。

#include <iostream>
using namespace std;

// 入力で与えられる変数
long long N, K;
long long A[200009];

// その他の変数
long long LastTime[200009];
long long LastCand[200009];

int main() {
	// 入力
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> A[i];

	// 配列の初期化
	// CurrentTime は現在の操作回数
	// CurrentCand は現在のアメの数
	long long CurrentTime = 0;
	long long CurrentCand = 0;
	for (int i = 0; i < N; i++) LastTime[i] = -1;
	for (int i = 0; i < N; i++) LastCand[i] = -1;

	// 手順 1: (u1, u2) を求める
	// CycleCand は 1 周期ごとに追加されるアメの数
	long long u1 = 0, u2 = 0;
	long long CycleCand = 0;
	while (true) {
		// 周期性が見つかる前に K 回目になってしまった
		if (CurrentTime == K) {
			cout << CurrentCand << endl;
			return 0;
		}
		// 周期性が見つかった
		if (LastTime[CurrentCand % N] != -1) {
			u1 = LastTime[CurrentCand % N];
			u2 = CurrentTime;
			CycleCand = CurrentCand - LastCand[CurrentCand % N];
			break;
		}
		// シミュレーション
		LastTime[CurrentCand % N] = CurrentTime;
		LastCand[CurrentCand % N] = CurrentCand;
		CurrentTime += 1;
		CurrentCand += A[CurrentCand % N];
	}

	// 手順 2: ギリギリまでを高速に求める
	// MaximumCycles は最大何周期分まで追加して良いか
	// FinalTime はギリギリまで考えたときに何回分の操作を終えたか
	// FinalCand はギリギリまで考えたときに何個のアメを追加したか
	long long MaximumCycles = (K - u2) / (u2 - u1);
	long long FinalTime = u2 + MaximumCycles * (u2 - u1);
	long long FinalCand = CurrentCand + MaximumCycles * CycleCand;

	// 手順 3: 最後はシミュレーション
	while (FinalTime < K) {
		FinalTime += 1;
		FinalCand += A[FinalCand % N];
	}

	// 出力
	cout << FinalCand << endl;
	return 0;
}