概要

駅 \(1\) から駅 \(N\) まで、各駅で決められた次の駅へ順番に移動していき、訪れる駅の総数を数える問題です。

考察

各駅 \(i\) から次に行ける駅は \(P_i\) の一つだけなので、駅 \(1\) を出発すると進む経路は一本道に決まります。分岐や選択肢がないため、ただ指示通りに次の駅へ移動し続ければよいです。

例えば、\(N = 5\)、\(P = [3, 4, 2, 5]\) の場合を考えてみましょう。

• 駅 \(1\) → \(P_1 = 3\) → 駅 \(3\)
• 駅 \(3\) → \(P_3 = 2\) → 駅 \(2\)
• 駅 \(2\) → \(P_2 = 4\) → 駅 \(4\)
• 駅 \(4\) → \(P_4 = 5\) → 駅 \(5\)（到着！）

訪れた駅は \(1, 3, 2, 4, 5\) の \(5\) 個です。

この問題は素朴なシミュレーション（実際に移動をたどる方法）で十分解けます。駅 \(1\) から駅 \(N\) に到達可能であることが保証されており、\(P_i \neq i\)（自分自身にはループしない）という制約もあるため、必ず有限ステップで駅 \(N\) に到達します。また、訪れる駅は最大 \(N\) 個なので、\(O(N)\) で十分間に合います。

アルゴリズム

1. 現在の駅 current を \(1\)（出発駅）、訪問駅数 count を \(1\) に初期化する。
2. current が \(N\) でない間、以下を繰り返す：
   • current を \(P_{\text{current}}\)（次の駅）に更新する。
   • count を \(1\) 増やす。
3. ループ終了後、count を出力する。

これは「リンクリストをたどる」操作と本質的に同じです。各駅が次の駅へのポインタ（\(P_i\)）を持っており、それを順にたどっていくだけです。

計算量

• 時間計算量: \(O(N)\)（最大で \(N\) 個の駅を訪れるため）
• 空間計算量: \(O(N)\)（配列 \(P\) を格納するため）

実装のポイント

• 配列 \(P\) は \(0\)-indexed で格納されるため、駅 \(i\)（\(1\)-indexed）の次の駅を取得するには P[i - 1] とアクセスする必要があります。

• 駅 \(N\) は最終目的地で \(P_N\) は存在しないため、入力は \(N - 1\) 個の値です。配列の範囲外アクセスが起きないよう、current != N の条件で必ずループを制御します。

  ソースコード

N = int(input())
P = list(map(int, input().split()))

current = 1
count = 1
while current != N:
    current = P[current - 1]
    count += 1
print(count)

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