概要

噂は友人関係を通じて拡散し、各日に「噂を知っている友人が \(T\) 人以上いる」未感染の生徒が新たに噂を知る。この過程をシミュレーションして、最終的に噂を知る生徒の総数を求めよ。

考察

この問題は、グラフ上で情報を伝播させるシミュレーション問題です。

• 各生徒を頂点、友人関係を辺とした無向グラフを考えます。
• 最初に噂を知っている生徒が与えられ、そこから「隣接する頂点のうち、\(T\) 人以上が既に噂を知っていたらその人も知る」というルールで拡散していきます。
• この伝播は、同時に起こるため、幅優先探索（BFS）のような形で処理するのが自然です。

素朴なアプローチとして、「毎日、全員について条件をチェックする」という方法がありますが、これは最大で \(N\) 日かかり、毎回 \(O(N)\) かかるため、全体で \(O(N^2)\) となり、制約が \(N \leq 2 \times 10^5\) なのでTLEします。

そこで重要なのは、各頂点が「噂を知っている友人の数」を持つカウンタを管理することです。最初に初期感染者の隣接頂点に対してカウントを増やし、カウントが \(T\) に達したらキューに入れるという方法で効率よくシミュレーションできます。

アルゴリズム

1. グラフを隣接リストで表現します。
2. knows[i]: 生徒 \(i\) が噂を知っているかどうかのフラグ。
3. informed_neighbors[i]: 生徒 \(i\) の周囲で既に噂を知っている友人の数。
4. 最初の \(K\) 人の知っている人に隣接する未感染の生徒に対し、informed_neighbors をインクリメント。\(T\) 以上になったらキューに追加。
5. キューから取り出して、その人が噂を知ったことにし、さらにその人の隣接する未感染の人に informed_neighbors を増やす。\(T\) に達したらキューに追加。
6. キューが空になったら終了。knows が True になっている人数を出力。

計算量

• 時間計算量: \(O(N + M)\)
  各頂点・辺が定数回しか処理されないため。
• 空間計算量: \(O(N + M)\)
  グラフの隣接リストと各種配列のサイズ。

実装のポイント

• knows 配列で既に噂を知っている人を管理し、再度キューから取り出したときに既に知っていたらスキップする処理を入れることで多重カウント防止。
• キューの初期状態は、最初の知っている人の隣接頂点のうち、informed_neighbors が \(T\) 以上になったものだけにする。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
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

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

    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)

    # Count how many informed neighbors each node has
    informed_neighbors = [0] * (N + 1)
    queue = deque()

    # Initialize counts and queue based on initial knowers
    for c in initial:
        for neighbor in adj[c]:
            if not knows[neighbor]:
                informed_neighbors[neighbor] += 1
                if informed_neighbors[neighbor] >= T:
                    queue.append(neighbor)

    # Propagate the rumor
    while queue:
        current = queue.popleft()
        if knows[current]:
            continue
        knows[current] = True
        for neighbor in adj[current]:
            if not knows[neighbor]:
                informed_neighbors[neighbor] += 1
                if informed_neighbors[neighbor] >= T:
                    queue.append(neighbor)

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

if __name__ == "__main__":
    main()

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