概要

この問題は、友人関係ネットワーク上で噂が閾値 \(T\) 以上の知人から伝播する条件で拡散する様子をシミュレーションし、最終的に噂を知る生徒の人数を求めるものです。

考察

噂の伝播プロセスは、各日において「まだ噂を知らない生徒のうち、噂を知っている友人の数が \(T\) 人以上になった生徒」が一斉に噂を知るという形で進行します。素朴なアプローチ（毎日全生徒をチェックする）では、最大 \(N\) 回の繰り返しが必要で、各日で \(N\) 人をチェックすると \(O(N^2)\) の時間がかかり、\(N\) が最大 \(2 \times 10^5\) なので実行時間制限に間に合いません。

効率的な解法として、キューを用いたBFS風のアプローチが有効です。ただし、標準的なBFSとは異なり、各頂点（生徒）が「噂を知っている友人」の数をカウントし、その数が閾値 \(T\) に達した時点で初めてキューに追加する点が特徴です。

アルゴリズム

1. グラフの構築: 生徒間の友人関係を無向グラフとして隣接リストで表現します。
2. 初期化: 初期状態で噂を知っている生徒をキューに追加し、knows 配列でマークします。
3. 伝播のシミュレーション:
   • キューから生徒を取り出し、その全ての友人（隣接頂点）に対して処理します。
   • 各友人について、まだ噂を知らない場合、その生徒の「噂を知っている友人の数」(informed_neighbors)を1増やします。
   • この数が閾値 \(T\) 以上になったら、その生徒を噂を知っている状態にし、キューに追加します。
4. 結果の計算: 最終的に knows 配列が True になっている生徒の数を数えます。

このアプローチでは、各辺（友人関係）は高々2回（双方向）処理されるため、効率的に伝播をシミュレーションできます。

計算量

• 時間計算量: \(O(N + M)\)
  • グラフの構築に \(O(N + M)\)
  • BFS風の処理で各頂点と各辺を定数回処理するため \(O(N + M)\)
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストに \(O(N + M)\)
  • knows, informed_neighbors 配列に \(O(N)\)

実装のポイント

• 無向グラフであるため、辺を双方向に追加する必要があります。

• キューには噂を「新しく知った」生徒のみを追加します（既知の生徒は追加しない）。

• 各生徒の「噂を知っている友人の数」を管理する informed_neighbors 配列が重要です。これにより、閾値 \(T\) を超えたタイミングを正確に検出できます。

• 入力値が大きいため、sys.stdin.read で一括読み込みを行うことで入力処理を高速化しています。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1

    initial = []
    for _ in range(K):
        c = int(data[idx]); idx += 1
        initial.append(c)

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)

    degree = [len(adj[i]) for i in range(N + 1)]
    informed_neighbors = [0] * (N + 1)
    knows = [False] * (N + 1)
    
    queue = deque()
    for c in initial:
        knows[c] = True
        queue.append(c)
    
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if knows[neighbor]:
                continue
            informed_neighbors[neighbor] += 1
            if informed_neighbors[neighbor] >= T:
                knows[neighbor] = True
                queue.append(neighbor)

    result = sum(knows[1:])
    print(result)

if __name__ == "__main__":
    main()

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