概要

各マスから「次にどこへ行くか」は完全に一意に決まるので、この問題は「マス \(1\) から始めて、関数グラフを \(K\) 回たどった先を求める問題」です。
\(K\) は最大 \(10^{18}\) と非常に大きいですが、状態数は \(N\) 個しかないため、途中から必ず同じ動きの繰り返しになります。

考察

1. 各マスの次の行き先は 1 つに決まる

この問題では、現在いるマス \(i\) が分かれば、次のマスは必ず 1 つに定まります。

• \(i = N\) なら常に \(N\)
• \(i = 1\) なら
  • \(A_1 + A_2\) が偶数 \(\Rightarrow 2\)
  • 奇数 \(\Rightarrow 1\)
• \(2 \le i \le N-1\) なら
  • \(A_i + A_{i+1}\) が偶数 \(\Rightarrow i+1\)
  • 奇数 \(\Rightarrow i-1\)

つまり、各マスから出る辺がちょうど 1 本のグラフだと考えられます。
このようなグラフは競技プログラミングで 関数グラフ と呼ばれます。

---

2. 素朴に \(K\) 回シミュレーションすると間に合わない

そのまま \(K\) 回移動をシミュレーションすると、計算量は \(O(K)\) です。
しかし \(K \le 10^{18}\) なので、これは到底間に合いません。

---

3. 状態数は \(N\) 個しかないので、必ずループに入る

今の状態は「現在いるマス番号」だけで表せます。
マスは \(1\) から \(N\) までの \(N\) 個しかないので、同じマスに 2 回到達した瞬間、その後の動きは完全に繰り返しになります。

つまり、移動列は必ず

• 最初のループに入る前の部分
• その後ずっと繰り返す周期部分

の 2 つに分かれます。

たとえば移動の様子が

\(1 \to 2 \to 3 \to 2 \to 3 \to 2 \to 3 \to \cdots\)

なら、

• ループに入る前：\(1\)
• 周期部分：\(2, 3\)

です。

---

4. 同じマスを初めて訪れた時刻を記録する

これを利用するために、

• visited[x] = マス \(x\) を最初に訪れた時刻
• order[t] = \(t\) 回移動した直後にいるマス

を記録しながら進みます。

ここでコードでは order[0] = 1 としており、
「0 回移動後はマス 1 にいる」 という形で扱っています。

もし今いるマス pos がすでに訪問済みなら、そこがループの開始点です。

• ループ開始位置を \(\mu\)
• ループ長を \(\lambda\)

とすると、

• \(\mu = \text{visited[pos]}\)
• \(\lambda = \text{現在の時刻} - \mu\)

で求まります。

その後、\(K\) 回後の位置は

• \(K\) がまだ記録済み範囲内なら order[K]
• そうでなければ周期部分に落として
  order[mu + (K - mu) % lambda]

で求められます。

---

5. なぜこれでよいのか

同じマスに戻ってきたということは、そのマスから先の遷移も前回と全く同じです。
したがって、以後の動きは周期 \(\lambda\) で繰り返されます。

よって、大きな \(K\) も「ループ部分のどこにいるか」だけ分かれば十分で、
\(K\) をそのまま扱う必要はありません。

アルゴリズム

1. \(N=1\) なら、何回移動しても答えは常に \(1\)。
2. 各マス \(i\) について、次のマス nxt[i] を前計算する。
3. pos = 1 から始めて、以下を繰り返す。
   • visited[pos] == -1 なら
     • visited[pos] = step
     • order.append(pos)
     • pos = nxt[pos]
     • step += 1
4. すでに訪れたマスに来たらループを発見したことになる。
   • mu = visited[pos]
   • cycle_len = step - mu
5. 答えを求める。
   • K < len(order) なら order[K]
   • それ以外なら order[mu + (K - mu) % cycle_len]

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 配列を 1-indexed にすると、問題文のマス番号とそのまま対応して実装しやすいです。

• order[0] は「0 回移動後」の位置であることに注意してください。これにより、答えがそのまま order[K] の形で扱えます。

• 偶奇判定は ((A[i] + A[i+1]) & 1) == 0 で行っています。

• ループ検出は「同じマスに再び来たら終了」で十分です。各マスからの遷移先が 1 つに決まっているためです。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = [0] + data[2:]

    if N == 1:
        print(1)
        return

    nxt = [0] * (N + 1)
    nxt[N] = N

    if ((A[1] + A[2]) & 1) == 0:
        nxt[1] = 2
    else:
        nxt[1] = 1

    for i in range(2, N):
        if ((A[i] + A[i + 1]) & 1) == 0:
            nxt[i] = i + 1
        else:
            nxt[i] = i - 1

    visited = [-1] * (N + 1)
    order = []

    pos = 1
    step = 0
    while visited[pos] == -1:
        visited[pos] = step
        order.append(pos)
        pos = nxt[pos]
        step += 1

    mu = visited[pos]
    cycle_len = step - mu

    if K < len(order):
        print(order[K])
    else:
        print(order[mu + (K - mu) % cycle_len])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。