概要

\(N\) 個のマスの上で、現在のマスの番号と書かれた整数の偶奇条件に従って \(K\) 回移動した後の目的地を求める問題です。移動回数 \(K\) が非常に大きいため、単純なシミュレーションではなく、移動の規則性（サイクル）を利用して解く必要があります。

考察

1. 移動の性質

この問題の最大の特徴は、「あるマスにいるとき、次にどのマスに移動するかは一意に決まっている」という点です。 移動規則を整理すると以下のようになります： - マス \(1\)：条件により マス \(2\) または \(1\) へ - マス \(i\) (\(2 \le i \le N-1\))：条件により マス \(i+1\) または \(i-1\) へ - マス \(N\)：常に マス \(N\) へ

一度移動先が決定すれば、同じマスからは必ず同じ場所へ移動するため、一度訪れたことのあるマスに再び戻ってきた場合、それ以降は同じ移動を繰り返す「サイクル（周期）」に入ることになります。

2. \(K\) の大きさとサイクルの検出

移動回数 \(K\) は最大で \(10^{18}\) と非常に大きいため、愚直に \(1\) 回ずつシミュレーションを行うと制限時間に間に合いません。 しかし、マスの総数 \(N\) は最大 \(2 \times 10^5\) です。鳩の巣原理により、遅くとも \(N+1\) 回移動するまでには、必ず過去に訪れたことのあるマスを再訪します。

したがって、以下の手順で効率的に解くことができます。 1. 実際に移動を行いながら、「どのマスに、何ステップ目に到達したか」を記録していく。 2. すでに訪れたマスに到達した瞬間、サイクルを検出する。 3. 残りの移動回数をサイクルの長さで割った余り（余り算）を利用して、最終的な目的地を特定する。

アルゴリズム

1. 前処理: 各マス \(i\) について、次の移動先 next_move[i] を計算して配列に格納します。
2. シミュレーションと記録:
   • 現在のマス curr を \(1\) とし、移動経路を記録するリスト path と、各マスの初回訪問ステップを記録する配列 visited_at を用意します。
   • \(K\) 回移動するか、サイクルを見つけるまで移動を繰り返します。
3. サイクルの利用:
   • ステップ \(s\) で過去に訪れたことのあるマス（ステップ \(m\) で訪問済み）に到達した場合：
     • サイクルの長さは \(L = s - m\) となります。
     • \(K\) 回目の移動後の状態は、サイクル内の \((K - m) \pmod L\) 番目の要素に対応します。
4. コーナーケース: \(N=1\) の場合や、サイクルに入る前に \(K\) 回の移動が終わる場合に注意して出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各マスからの移動先の計算に \(O(N)\)、サイクルの検出までに最大 \(N+1\) 回の移動をシミュレーションするため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 移動先を保持する配列や、訪問記録を保持する配列に \(O(N)\) のメモリを使用します。

実装のポイント

• 1-indexed と 0-indexed: 問題文のマス番号は \(1\) から始まりますが、プログラミング言語の配列は \(0\) から始まることが多いため、添字の扱いに注意が必要です。

• サイクルの計算: \(K\) 回の移動のうち、サイクルに入る前の移動回数 \(m\) を差し引いてから、サイクルの長さ \(L\) で割った余りを計算します。式にすると cycle[(K - m) % L] のようになります。

  ソースコード

import sys

# この問題は、すごろくの盤面上の移動が決定論的であり、マスの数が N 個であるため、
# K 回の移動の途中で必ず同じマスを再訪するか、特定のマスに留まることになります。
# K が非常に大きいため、周期性（サイクル）を検出することで効率的に解くことができます。

def solve():
    # 入力をすべて読み込み、スペースで分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: マスの数, K: 移動回数
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各マスに書かれた整数
    A = list(map(int, input_data[2:]))

    # マスが1つしかない場合、常にマス1に留まります。
    if N == 1:
        print(1)
        return

    # 各マス i からの次の移動先をあらかじめ計算しておきます。
    # マス番号は1からNまでなので、サイズ N+1 の配列を使用します。
    next_move = [0] * (N + 1)
    
    # マス 1 の移動規則
    # A1 + A2 が偶数ならマス 2 へ、そうでなければマス 1 に留まる。
    if (A[0] + A[1]) % 2 == 0:
        next_move[1] = 2
    else:
        next_move[1] = 1
        
    # マス N の移動規則
    # 常にマス N に留まる。
    next_move[N] = N
    
    # マス 2 から N-1 までの移動規則
    # Ai + Ai+1 が偶数ならマス i+1 へ、そうでなければマス i-1 に戻る。
    for i in range(2, N):
        # A[i-1] はマス i の値、A[i] はマス i+1 の値に対応します。
        if (A[i-1] + A[i]) % 2 == 0:
            next_move[i] = i + 1
        else:
            next_move[i] = i - 1
    
    # 現在のマスを追跡し、サイクル検出を行います。
    curr = 1
    path = [curr]
    # visited_at[i] はマス i を最初に訪れた時のステップ数を記録します。
    visited_at = [-1] * (N + 1)
    visited_at[curr] = 0
    
    # 最大で N+1 回移動すれば、必ずサイクルに到達するか K 回の移動が終わります。
    for step in range(1, N + 2):
        # 指定された移動回数 K に達した場合は終了
        if step > K:
            break
        
        # 次のマスへ移動
        curr = next_move[curr]
        
        # 既に訪れたマスに到達した場合、サイクルを検出
        if visited_at[curr] != -1:
            # サイクルが始まったステップ
            m = visited_at[curr]
            # サイクルの構成要素を抽出
            cycle = path[m:]
            cycle_len = len(cycle)
            # K 回目の移動後のマスをサイクルの周期性から計算
            ans = cycle[(K - m) % cycle_len]
            print(ans)
            return
        
        # 訪問記録を更新
        visited_at[curr] = step
        path.append(curr)
    
    # K が小さく、サイクルを検出する前にシミュレーションが終了した場合
    if K < len(path):
        print(path[K])

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。