概要

グラフ上で噂が段階的に広がるシミュレーション問題です。初めに噂を知っている \(K\) 人から出発し、「噂を知っている友人が \(T\) 人以上」いる生徒に次々と噂が伝播していき、最終的に噂を知っている生徒の人数を求めます。

考察

素朴なアプローチとその問題点

最も単純な方法は、「1日をシミュレーション」することです。毎日、全生徒を走査して、噂を知らない各生徒について「噂を知っている友人が何人いるか」を数え、\(T\) 人以上なら新たに噂を知る、という処理を繰り返します。

しかし、この方法では最悪の場合、1日に1人しか新たに噂を知らない可能性があり、毎日全生徒・全辺を走査すると \(O(N \times (N + M))\) となり、\(N, M\) が \(2 \times 10^5\) のときTLEになります。

重要な気づき：BFS的な伝播

噂の拡散は、BFS（幅優先探索）に似た構造を持っています。

• 各生徒について「噂を知っている友人の数」をカウンタ friend_count で管理する
• カウンタがちょうど \(T\) に達した瞬間にキューに入れる
• キューから取り出した生徒が噂を知り、その友人のカウンタを更新する

こうすることで、各辺は高々1回しか処理されず、効率的にシミュレーションできます。

具体例

例えば \(N=5, T=2\) で、生徒1と生徒2が最初に噂を知っており、辺が \((1,3), (2,3), (3,4), (4,5)\) のとき：

1. 初期状態: 生徒1, 2が噂を知っている。生徒3の friend_count は2（友人1と2が知っている）→ 閾値 \(T=2\) に達するのでキューに入る
2. 生徒3が噂を知る: 生徒4の friend_count が1に増える → まだ \(T=2\) 未満なのでキューには入らない
3. 終了: キューが空になり、最終的に噂を知っているのは生徒1, 2, 3の3人

アルゴリズム

1. 隣接リスト adj を構築する
2. 初期の噂を知っている生徒について knows[c] = True とする
3. 初期の噂を知っている各生徒 \(c\) について、その友人 \(nb\) の friend_count[nb] を1増やす。もし friend_count[nb] がちょうど \(T\) になったら、\(nb\) をキューに入れる
4. キューから生徒 node を取り出し、まだ噂を知らず friend_count[node] >= T であれば：
   • knows[node] = True にする
   • node の各友人 \(nb\) について friend_count[nb] を1増やし、ちょうど \(T\) に達したらキューに入れる
5. キューが空になったら、knows が True の生徒を数えて出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 各生徒は高々1回キューに入り、各辺は高々2回（両端点から1回ずつ）処理される
• 空間計算量: \(O(N + M)\)
  • 隣接リスト、カウンタ配列、キューなどに使用

実装のポイント

• キューに入れるタイミング: friend_count がちょうど \(T\) になった瞬間のみキューに追加する。これにより同じ生徒が何度もキューに入ることを防ぎ、効率を保てる

• キューから取り出した際の確認: 万が一重複してキューに入った場合に備え、knows[node] が既に True ならスキップする

• 同時伝播の正しさ: 問題文では「すべての新たな伝達は同時に発生」とありますが、カウンタが閾値に達した時点でキューに入れるBFS方式でも結果は同じです。なぜなら、ある生徒が噂を知るかどうかは「最終的に噂を知っている友人の数」で決まり、伝播の順序によらないからです

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    knows = [False] * (N + 1)
    initial = []
    for i in range(K):
        c = int(input_data[idx]); idx += 1
        initial.append(c)
        knows[c] = True
    
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # count of friends who know the rumor
    friend_count = [0] * (N + 1)
    
    queue = deque()
    
    # Initialize: for each initial knower, update their friends' counts
    for c in initial:
        for nb in adj[c]:
            if not knows[nb]:
                friend_count[nb] += 1
                if friend_count[nb] == T:
                    queue.append(nb)
    
    while queue:
        node = queue.popleft()
        if knows[node]:
            continue
        # Check if still meets threshold (it should since we only enqueue at threshold)
        if friend_count[node] >= T:
            knows[node] = True
            for nb in adj[node]:
                if not knows[nb]:
                    friend_count[nb] += 1
                    if friend_count[nb] == T:
                        queue.append(nb)
    
    print(sum(knows[1:N+1]))

main()

---

この解説は claude4.6opus-thinking によって生成されました。