概要

\(N\) 人のメンバーがルールに従ってメッセージを順次に転送していくとき、誰かが 2 回目にメッセージを受け取る（既読になる）までに、合計で何人のメンバーがメッセージを受け取ったかを求める問題です。

考察

この問題は、グラフ理論の言葉で言えば「各頂点から出次数が 1 の有向グラフ」における移動をシミュレーションする問題です。

重要な気づき

1. 終了条件: 誰かが「2 回目」にメッセージを受け取った瞬間に転送が止まります。これは、一度訪れたメンバー（頂点）を記録しておき、再びそのメンバーに到達したかどうかを判定すればよいことを意味します。
2. 人数のカウント: メッセージは一人ずつ順番に渡されていきます。まだメッセージを受け取っていない新しいメンバーに渡るたびに、カウントを \(+1\) していきます。
3. 計算量: メンバーの人数 \(N\) は最大で \(2 \times 10^5\) です。一度訪れたメンバーを再び訪れたら終了するため、シミュレーションのステップ数は最大でも \(N\) 回程度です。したがって、愚直に一人ずつ転送を追いかけても十分に間に合います。

具体例

例えば \(N=4\) で、転送先が \(P_1=2, P_2=3, P_3=4, P_4=2\) の場合を考えます。 - メンバー 1 が受け取る（1人目：既読 [1]） - 1 から \(P_1=2\) へ転送。メンバー 2 が受け取る（2人目：既読 [1, 2]） - 2 から \(P_2=3\) へ転送。メンバー 3 が受け取る（3人目：既読 [1, 2, 3]） - 3 から \(P_3=4\) へ転送。メンバー 4 が受け取る（4人目：既読 [1, 2, 3, 4]） - 4 から \(P_4=2\) へ転送。メンバー 2 は既に既読なので、ここで終了。 - 結果：4人

アルゴリズム

1. 既読情報の管理: 長さ \(N+1\) の真偽値配列 visited を用意し、すべて False で初期化します。
2. シミュレーション:
   • 現在のメンバー current を 1 に設定し、カウント count を 0 にします。
   • visited[current] が False である間、以下の操作を繰り返します：
     1. visited[current] を True にする（既読にする）。
     2. count を 1 増やす。
     3. current を次の転送先である \(P_{current}\) に更新する。
3. 出力: 繰り返しが終了したときの count の値を出力します。

計算量

• 時間計算量: \(O(N)\)
  • メッセージの転送を 1 ステップずつ辿ります。各メンバーを訪問するのは最大 1 回であるため、メンバーの人数 \(N\) に比例した時間で終わります。
• 空間計算量: \(O(N)\)
  • 転送先のリスト \(P\) と、既読状態を記録する配列 visited を保持するために \(N\) に比例したメモリを使用します。

実装のポイント

• 1-indexed の扱い: 問題文ではメンバー番号が 1 から \(N\) で与えられます。Python のリストは 0 から始まるため、p[current - 1] のようにインデックスを調整するか、リストのサイズを \(N+1\) にして調整するとミスを防げます。

• 効率的な入力: \(N\) が大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと高速に動作します。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # メンバーの人数 N を取得
    n = int(input_data[0])
    # 各メンバー i の転送先 P_i のリストを取得
    # P[i-1] が メンバー i の転送先 P_i に対応します
    p = list(map(int, input_data[1:]))
    
    # メッセージを受け取ったかどうかを記録する配列（1-indexedに対応するため n+1 サイズ）
    visited = [False] * (n + 1)
    
    # メンバー 1 から転送を開始
    current = 1
    count = 0
    
    # まだメッセージを受け取っていないメンバーである限り転送を続ける
    while not visited[current]:
        # 現在のメンバーを「既読」にする
        visited[current] = True
        # 受け取った人数をカウント
        count += 1
        # 次の転送先メンバーを更新
        # メンバー i の転送先は P_i (リストでは p[i-1])
        current = p[current - 1]
        
    # メッセージを受け取った延べ人数（ユニークな人数）を出力
    print(count)

if __name__ == '__main__':
    solve()

---

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