概要

各駅から次の駅が決まっている路線上で、駅 \(1\) から駅 \(N\) に到達するまでに訪れる駅の数を求めます。

考察

この問題は、駅から駅への移動が一意に定まっているので、単純にシミュレーションすれば解けそうです。つまり、駅 \(1\) から出発して、指示に従って次の駅に移動し、駅 \(N\) にたどり着くまで何ステップかかったかを数えるだけです。

しかし、もしループがある場合や非常に長い経路がある場合、ナイーブな実装でも間に合うか不安になるかもしれません。しかし制約には「駅 \(1\) から駅 \(N\) に到達可能」とあるので、途中で無限ループすることはなく、また \(N\) は最大 \(2 \times 10^5\) なので、全駅を一回ずつ通るとしても十分間に合います。

したがって、愚直にシミュレーションを行うのが適切です。各駅から次の駅への遷移を配列に持っておき、現在地を更新しながらカウントを増やすことで答えを得られます。

例えば、入力が以下のような場合：

N = 5
P = [2, 3, 4, 5]

これは、駅1→2→3→4→5と一直線に進むだけなので、訪れる駅の数は5個です。

もう一つ例を見てみましょう：

N = 4
P = [3, 3, 4]

これは、 - 駅1 → 駅3 - 駅2 → 駅3 - 駅3 → 駅4

となるので、駅1からスタートすると、 駅1 → 駅3 → 駅4 となり、訪れる駅の数は3個です。

このように、ただ一つ前の情報をもとに次の駅に進んでいけば良いので、ループや再帰など複雑な処理は必要ありません。

アルゴリズム

1. 各駅 \(i\) からの次の駅 \(P_i\) の情報をリストとして保持します（ただし、0-indexedに変換して扱いやすくします）。
2. 現在位置を駅 \(1\)（0-indexedでは 0）とし、訪れた駅の数を初期値 \(1\) としておきます。
3. 現在位置が駅 \(N\)（0-indexedでは N-1）になるまで、次の駅に移動し続け、その都度カウントを増やします。
4. 最終的なカウントを出力します。

計算量

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

時間計算量は、最悪の場合すべての駅を通る可能性があるため、\(O(N)\) です。空間計算量も、次の駅の情報を持つ配列のサイズが \(N-1\) であり、定数倍を除けば \(O(N)\) となります。

実装のポイント

• 駅番号は1-indexedで与えられるので、内部処理では0-indexedに変換すると扱いやすくなります。
• 終了条件は現在位置が N-1（0-indexedでの駅N）になったときです。
• 入力の受け取りを高速化するため、sys.stdin.read を使用しています。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:]))
    
    # 駅番号は1-indexedなので、P[i-1] が 駅iから次の駅を示す
    # next_station[i] = 駅i+1から次の駅 (0-indexed)
    next_station = [p - 1 for p in P]
    
    current = 0  # 駅1 (0-indexed)
    count = 1    # 駅1を含む
    
    while current != N - 1:  # 駅Nに到達するまで (N-1は0-indexed)
        current = next_station[current]
        count += 1
        
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。