概要

駅1から駅Nまで、各駅から決まった次の駅へ移動する列車を乗り継いで到達するまでに訪れる駅の数を求める問題です。

考察

この問題では、各駅iからは必ず駅\(P_i\)へ移動するという単純な構造になっています。駅1から出発して駅Nに到達するまでの経路は、この移動規則によって一意に決まります。つまり、駅1 → 駅\(P_1\) → 駅\(P_{P_1}\) → … というように、駅Nに到達するまで移動を繰り返すことで経路を求めることができます。

素朴なアプローチとして、実際に駅1から駅Nまで移動しながら経由駅を記録していく方法が考えられます。入力サイズが最大20万駅と大きいですが、各駅から移動先が1つに決まっているため、単純に移動をシミュレーションするだけで効率的に解くことができます。

アルゴリズム

1. 駅1を現在位置として初期化する
2. 現在位置が駅Nになるまで以下を繰り返す：
   • 現在位置を経路に追加する
   • 現在位置の次の駅（\(P_{current-1}\)）に移動する
3. 駅Nに到達したら、駅Nも経路に追加する
4. 経路リストの長さを出力する

このアルゴリズムは、駅1から駅Nまでの経路を実際にたどることで、経由する駅の数を正確に数えます。問題の制約で駅1から駅Nに必ず到達できることが保証されているため、無限ループになる心配はありません。

計算量

• 時間計算量: \(O(K)\)（Kは駅1から駅Nまでの経由駅数）
• 空間計算量: \(O(K)\)（経路を保存するためのリスト）

最大でN駅分の経路を保存する可能性があるため、最悪ケースでは\(O(N)\)のメモリを使用しますが、制約条件内で十分に処理できます。

実装のポイント

• 配列のインデックスに注意：駅iの情報は配列のi-1番目に格納されています

• 駅Nに到達した時点でループを終了する

• 最後に駅N自体も経路に追加することを忘れない

• 入力読み込み時に、駅Nの情報がないため\(N-1\)個のデータしか与えられない点に注意

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    P = list(map(int, data[1:1+n-1]))
    
    path = []
    current = 1
    while current != n:
        path.append(current)
        current = P[current-1]
    path.append(n)
    
    print(len(path))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。