概要

この問題は、各駅から次の行き先が一つに決まっている路線において、駅 \(1\) から出発して目的地である駅 \(N\) に到着するまでに、いくつの駅を訪問するかを求めるシミュレーション問題です。

考察

この問題のポイントは、「各駅からの行き先が一つに固定されている」という点です。

駅 \(i\) に着くと、次は必ず駅 \(P_i\) へ向かうことになります。つまり、駅 \(1\) からスタートして駅 \(N\) に着くまでの経路は一本道であり、迷う余地がありません。したがって、問題文の指示通りに「今いる駅」を更新しながら、駅 \(N\) に着くまで移動を繰り返すことで正解を導き出すことができます。

制約を確認すると、駅の数 \(N\) は最大で \(2 \times 10^5\) です。最悪の場合、すべての駅を一度ずつ通ることになりますが、その場合でも計算回数は \(2 \times 10^5\) 程度です。これは一般的なプログラミング言語の制限時間（通常 2 秒程度）内で十分に間に合う計算量です。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 現在の駅を指す変数 curr を \(1\) で初期化します。
2. 訪れた駅の数をカウントする変数 count を \(1\) で初期化します（出発駅である駅 \(1\) を含むため）。
3. curr が \(N\) になるまで、以下の処理を繰り返します。
   • curr を、現在の駅からの行き先である \(P_{curr}\) に更新します。
   • count を \(1\) 増やします。
4. 最終的な count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 駅 \(1\) から駅 \(N\) に到達するまでに、最大で \(N\) 個の駅を訪問するため、ループの回数は最大 \(N\) 回となります。
• 空間計算量: \(O(N)\)
  • 各駅の行き先 \(P_i\) をリスト（配列）に格納するために、駅の数に比例したメモリを使用します。

実装のポイント

• インデックスの対応: 問題文では駅番号が \(1\) から \(N\) で与えられますが、多くのプログラミング言語（Python など）のリストは \(0\) 番目から始まります。駅 \(i\) の行き先 \(P_i\) をリスト p に格納する場合、駅 curr の次の駅は p[curr - 1] となる点に注意が必要です。

• 入力の読み込み: \(N\) が大きいため、効率的に入力を読み込むことが推奨されます。Python の場合、sys.stdin.read().split() を使うことで、大量の数値を一括で取得できます。

  ソースコード

import sys

def main():
    # 入力をすべて読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 駅の数 N
    n = int(input_data[0])
    # 各駅からの行き先 P_i (i=1 から N-1 まで)
    # P[i-1] が駅 i からの行き先に対応するようにリスト化します
    p = list(map(int, input_data[1:]))
    
    # 現在の駅 (1からスタート)
    curr = 1
    # 訪れた駅の数 (出発駅を含むため1で初期化)
    count = 1
    
    # 目的地である駅 N に到着するまで繰り返します
    while curr != n:
        # 駅 i からの行き先は P_i です。
        # リスト p は 0-indexed なので、駅 curr からの行き先は p[curr - 1] です。
        curr = p[curr - 1]
        # 訪れた駅の数をカウント
        count += 1
    
    # 結果を出力
    print(count)

if __name__ == "__main__":
    main()

---

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