概要

すごろくの盤面上で決定的なルールに従って \(K\) 回移動したとき、最終的にいるマスの番号を求める問題です。\(K\) が最大 \(10^{18}\) と非常に大きいため、愚直なシミュレーションではなくサイクル検出を用いて高速化します。

考察

移動ルールの整理

各マス \(i\) での移動は、隣接するマスの値の和の偶奇だけで決まります。

• マス \(N\): 常にその場に留まる（ゴール）
• マス \(1\): \(A_1 + A_2\) が偶数なら前進（マス \(2\) へ）、奇数なら留まる
• マス \(i\)（\(2 \le i \le N-1\)）: \(A_i + A_{i+1}\) が偶数なら前進（マス \(i+1\) へ）、奇数なら後退（マス \(i-1\) へ）

重要な気づきとして、各マスでの移動方向は配列 \(A\) の値だけで事前に決まり、何回目の移動かによらず常に同じです。つまり、状態は「現在いるマスの番号」だけで完全に決まります。

素朴なシミュレーションの問題点

\(K\) が最大 \(10^{18}\) なので、\(K\) 回のシミュレーションを1ステップずつ行うと到底間に合いません（TLE）。

サイクル検出による高速化

状態は現在のマス番号 \(1\) から \(N\) のいずれかなので、高々 \(N\) ステップ以内に同じマスを再び訪れます。同じマスに戻ったということは、そこから先は全く同じ動きの繰り返し（サイクル）になります。

具体例: \(N=5\), \(K=10^{18}\) で、移動の履歴が \(1 \to 2 \to 3 \to 2 \to 3 \to 2 \to \cdots\) となった場合、ステップ1でマス2、ステップ2でマス3、ステップ3で再びマス2に戻ります。サイクルの開始はステップ1、サイクル長は2です。残りの移動回数 \((K - 1) \mod 2\) を計算すれば、サイクル内のどの位置にいるか分かります。

アルゴリズム

1. \(N = 1\) なら答えは \(1\)。
2. マス \(1\) からシミュレーションを開始する。
3. 各ステップで「現在のマス番号」を記録し、過去に同じマス番号が出現したか確認する。
4. 同じマスが見つかった場合（サイクル検出）:
   • サイクル開始ステップ \(s\) とサイクル長 \(L\)（= 現在のステップ \(- s\)）を求める。
   • 残りの移動回数を \((K - s) \mod L\) で計算し、履歴から \(s + ((K - s) \mod L)\) 番目の位置を出力する。
5. サイクルが見つかる前に \(K\) ステップ分のシミュレーションが終わった場合: その時点のマス番号を出力する。

状態数は高々 \(N\) 個なので、最大でも \(N + 1\) ステップ以内にサイクルが検出されます。

計算量

• 時間計算量: \(O(N)\)（サイクルは高々 \(N\) ステップで検出される）
• 空間計算量: \(O(N)\)（履歴の保存および訪問管理）

実装のポイント

• 偶奇判定: \(A_i + A_{i+1}\) の偶奇は、各 \(A_i\) の偶奇だけで決まります。(A[i-1] + A[i]) % 2 で判定できます。

• 1-indexed と 0-indexed の変換: 問題文ではマスは1-indexedですが、配列 \(A\) は0-indexedで保持しているため、マス \(i\) の値は A[i-1] となります。

• 固定点もサイクルの一種: マス \(N\) に到達して留まる場合やマス \(1\) で留まる場合は、サイクル長1のサイクルとして自然に検出されます（2回連続で同じマスが記録されるため）。

• \(K\) が小さい場合: サイクル検出より先に \(K\) 回の移動が終わることもあるため、ループ回数の上限を \(\min(K, 2N+10)\) 程度に設定しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = list(map(int, input_data[2:2+N]))
    
    if N == 1:
        print(1)
        return
    
    # Precompute direction for each position (1-indexed)
    # For position i (1-indexed):
    #   i == N: stay at N
    #   i == 1: if (A[0]+A[1]) even -> go to 2, else stay at 1
    #   2 <= i <= N-1: if (A[i-1]+A[i]) even -> go to i+1, else go to i-1
    
    # Simulate but detect cycles
    # The position is bounded [1, N], and once we reach N we stay there.
    # Also, if at position 1 and direction is "stay", we stay forever.
    # Between positions 2..N-1, we either go forward or backward.
    # Key insight: movement is deterministic, so we can simulate and detect cycles.
    
    # But K can be up to 10^18, so we need cycle detection.
    # The state is just the current position (1 to N), so cycle length <= N.
    
    pos = 1  # 1-indexed
    
    # We'll simulate and track visited states to detect cycles
    # Since state space is at most N, cycle must occur within N steps
    
    history = []
    pos_to_step = {}
    
    for step in range(min(K, 2 * N + 10)):
        if pos in pos_to_step:
            # Found a cycle
            cycle_start = pos_to_step[pos]
            cycle_len = step - cycle_start
            remaining = (K - cycle_start) % cycle_len
            print(history[cycle_start + remaining])
            return
        pos_to_step[pos] = step
        history.append(pos)
        
        # Compute next position
        if pos == N:
            next_pos = N
        elif pos == 1:
            if (A[0] + A[1]) % 2 == 0:
                next_pos = 2
            else:
                next_pos = 1
        else:
            if (A[pos-1] + A[pos]) % 2 == 0:
                next_pos = pos + 1
            else:
                next_pos = pos - 1
        
        pos = next_pos
    
    # If no cycle detected within the simulation, we must have simulated enough
    # Or K was small enough
    if len(history) == K:
        # We did K steps of recording but haven't done the final move accounting
        # Actually history[i] = position after i moves (history[0] = position after 0 moves = start)
        # We need position after K moves = pos (which is the current position after the loop)
        print(pos)
    else:
        # Check if we ended up in a fixed point (pos == N or pos == 1 staying)
        # In that case pos_to_step would have caught it as a cycle of length 1
        # on the second visit. Let's just handle it:
        print(pos)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。