概要

この問題は、有向グラフにおいて「ある始点 \(S\) から出発して、最大 \(K_j\) ステップ以内にすべての頂点に到達できるような始点 \(S\) の個数」を各クエリに対して求める問題です。

考察

1. 問題の言い換え

噂の伝播ルールをグラフの言葉で整理します。 生徒を「頂点」、伝達関係を「有向辺」とする有向グラフを考えます。

「ステップ \(0\) からステップ \(K_j\) までの間に、すべての生徒が少なくとも \(1\) 回は噂を受け取る」という条件を考えます。 ある生徒 \(i\) がステップ \(t\) （\(0 \le t \le K_j\)）で噂を受け取るということは、始点 \(S\) から生徒 \(i\) への最短経路の長さ（最短距離）が \(K_j\) 以下であることと同値です。

したがって、すべての生徒がステップ \(K_j\) までに噂を受け取るための条件は、以下の2つに分解できます。 1. 始点 \(S\) からすべての頂点に到達可能である。 2. 始点 \(S\) から最も遠い頂点への最短距離が \(K_j\) 以下である。

始点 \(S\) からすべての頂点への最短距離の最大値を \(D(S)\) とします（すべての頂点に到達できない場合は \(D(S) = \infty\) とします）。 このとき、クエリ \(K_j\) に対する条件は 「\(D(S) \le K_j\) を満たす \(S\) の個数を求める」 と非常にシンプルに言い換えることができます。

2. 高速化の検討

クエリの個数 \(Q\) は最大で \(2 \times 10^5\) と非常に大きいため、クエリごとにグラフを探索していては実行時間制限に間に合いません（TLEになります）。

しかし、グラフの頂点数 \(N\) は最大で \(2000\) と比較的小さいです。 そこで、あらかじめすべての頂点 \(S\) （\(1 \le S \le N\)）を始点とした最短距離を求めておくアプローチを取ります。

各 \(S\) について \(D(S)\) を計算しておけば、あとは \(D(S)\) の値の分布を記録した累積和配列を用意することで、各クエリに対して \(O(1)\) で回答できるようになります。

---

アルゴリズム

1. 各始点からの最短経路探索 (BFS) 各頂点 \(S \in \{1, 2, \ldots, N\}\) を始点として、幅優先探索（BFS）を行います。

   • BFSで訪問した頂点数が \(N\) 未満の場合、すべての頂点に到達できないため、この \(S\) はどのようにしても全員に噂を届けることができません。この場合は \(D(S) = \infty\) （実装上は \(N+1\)）とします。
   • 訪問した頂点数が \(N\) の場合、最後に訪問した頂点（BFSのキューの最後尾にある頂点）への最短距離が \(D(S)\) となります。

2. 頻度配列と累積和の計算 サイズ \(N+2\) の配列 counts を用意し、各 \(S\) に対する \(D(S)\) の値を集計します。

   • counts[d] = 最大最短距離 \(D(S)\) がちょうど \(d\) であるような始点 \(S\) の個数

この counts の累積和配列 pref を作成します。 - pref[k] = \(D(S) \le k\) となる始点 \(S\) の個数 （すなわち、ステップ \(k\) 以内に全員に噂が伝わるような始点の個数）

1. クエリへの解答 各クエリ \(K_j\) に対し、以下のように答えます。
   • \(K_j \ge N\) の場合：\(N\) ステップより多くかかることはないため、pref[N] を出力します。
   • \(K_j < N\) の場合：pref[K_j] を出力します。

---

計算量

• 時間計算量: \(O(N(N + M) + Q)\)

  • 各頂点からのBFSに \(O(N + M)\) かかります。これを \(N\) 回行うため、前処理のグラフ探索に \(O(N(N + M))\) かかります。\(N \le 2000, M \le 50000\) であるため、最悪の場合でも約 \(10^8\) 回の計算量となり、定数倍の軽いBFSであれば実行時間制限に十分間に合います。
  • クエリの処理は、累積和配列へのアクセスのみであるため1回あたり \(O(1)\)、全体で \(O(Q)\) です。

• 空間計算量: \(O(N + M)\)

  • グラフの隣接リストの保持に \(O(N + M)\)、BFS用の配列や累積和配列に \(O(N)\) のメモリを使用します。

---

実装のポイント

Pythonで \(10^8\) 回程度のループを制限時間内に実行するためには、いくつかの高速化テクニックが有効です。

• 配列の再確保を避ける 各BFSのたびに dist 配列（距離を記録する配列）を [-1] * N で初期化し直すと、初期化のオーバーヘッドが無視できなくなります。 提示されたコードでは、BFSで訪れた頂点（queue に入っている頂点）のみをピンポイントで -1 に戻すことで、初期化にかかる時間を \(O(N)\) から「実際に探索した頂点数」の \(O(\text{visited})\) に削減し、大幅な高速化を実現しています。

• 入出力の高速化 sys.stdin.read を用いて入力を一括で取得し、出力も sys.stdout.write でまとめて出力することで、入出力ボトルネックを解消しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    Q = int(input_data[2])
    
    adj = [[] for _ in range(N)]
    idx = 3
    for _ in range(M):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        adj[u].append(v)
        idx += 2
        
    adj = tuple(tuple(x) for x in adj)
    
    dist = [-1] * N
    queue = [0] * N
    counts = [0] * (N + 2)
    
    for s in range(N):
        dist[s] = 0
        queue[0] = s
        head = 0
        tail = 1
        while head < tail:
            u = queue[head]
            head += 1
            nd = dist[u] + 1
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = nd
                    queue[tail] = v
                    tail += 1
        if tail < N:
            counts[N+1] += 1
        else:
            max_d = dist[queue[N-1]]
            counts[max_d] += 1
            
        for i in range(tail):
            dist[queue[i]] = -1
            
    pref = [0] * (N + 2)
    cur = 0
    for i in range(N + 2):
        cur += counts[i]
        pref[i] = cur
        
    ans = []
    for _ in range(Q):
        k = int(input_data[idx])
        idx += 1
        if k >= N:
            ans.append(str(pref[N]))
        else:
            ans.append(str(pref[k]))
            
    sys.stdout.write('\n'.join(ans) + '\n')

if __name__ == '__main__':
    solve()

---

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