概要

有向グラフ上で噂が同期的に広まる仕組みにおいて、各始点 \(S\) について \(K\) ステップ以内に全員に噂が届くかを判定する問題。核心は「各生徒が初めて噂を受け取るステップ＝始点からの最短距離」という観察にある。

考察

重要な気づき：初回到達ステップ＝最短距離

問題の定義では \(A_t\) は「ステップ \(t\) で噂を受け取る生徒の集合」であり、過去に噂を聞いた生徒でも再び含まれうる。しかし、各生徒 \(v\) が初めて噂を受け取るステップ \(f(v) = \min\{t \mid v \in A_t\}\) に注目すると、これは始点 \(S\) から \(v\) への有向グラフ上の最短距離 \(d(S, v)\) に一致する。

証明のスケッチ：

• \(f(v) \leq d(S, v)\)：最短経路 \(S = w_0 \to w_1 \to \cdots \to w_d = v\) があるとき、\(w_0 \in A_0\) より \(w_1 \in A_1\)、\(w_1 \in A_1\) より \(w_2 \in A_2\)、…と順に伝播して \(v \in A_d\) が保証される。
• \(f(v) \geq d(S, v)\)：\(v \in A_t\) なら帰納法より、ある \(u \in A_{t-1}\) から辺 \((u,v)\) が存在し \(d(S,v) \leq d(S,u) + 1 \leq t\)。

クエリへの帰着

クエリ \(K_j\) に対して、\(S\) が条件を満たすのは「すべての生徒 \(v\) について \(d(S, v) \leq K_j\)」と同値。つまり、

\[\max_{1 \leq v \leq N} d(S, v) \leq K_j\]

を満たす \(S\) の個数を数えればよい。

アルゴリズム

1. 全始点 BFS：各生徒 \(S\)（\(1 \leq S \leq N\)）を始点として有向グラフ上で BFS を行い、全頂点への最短距離を計算する。到達不能な頂点があれば \(\text{max\_dist}[S] = \infty\)（実装上は \(N+1\)）、そうでなければ \(\text{max\_dist}[S] = \max_v d(S, v)\) とする。

2. 度数分布の前処理：\(\text{max\_dist}[S]\) の値ごとに個数を数え、累積和を取る。\(\text{ans}[k] = |\{S \mid \text{max\_dist}[S] \leq k\}|\) を \(k = 0, 1, \ldots, N\) について前計算する。

3. クエリ応答：各クエリ \(K_j\) に対して \(\text{ans}[K_j]\) を \(O(1)\) で出力する。

具体例

グラフ：\(1 \to 2,\ 2 \to 3,\ 1 \to 3\) で \(N=3\) の場合。 - \(S=1\)：\(d(1,1)=0,\ d(1,2)=1,\ d(1,3)=1\) → \(\text{max\_dist}=1\) - \(S=2\)：\(d(2,3)=1\) だが \(d(2,1)=\infty\) → \(\text{max\_dist}=\infty\) - \(S=3\)：どこにも行けない → \(\text{max\_dist}=\infty\)

\(K=1\) の答えは \(1\)（\(S=1\) のみ有効）。

計算量

• 時間計算量: \(O(N(N + M) + Q)\)
  • \(N\) 回の BFS がそれぞれ \(O(N + M)\)、クエリは前計算後 \(O(1)\) ずつ
• 空間計算量: \(O(N + M)\)
  • グラフの隣接リストと BFS 用配列

実装のポイント

• BFS は標準的なキューを用いた実装で、各頂点を初めて訪問したときのみキューに追加する。問題の \(A_t\) の定義では再訪問が起こりうるが、初回到達のみが重要なので通常の BFS で十分。

• 到達不能な頂点がある場合を正しく処理するため、BFS で訪問した頂点数をカウントし、\(N\) 未満なら \(\text{max\_dist}[S]\) を \(N+1\)（\(K\) の最大値 \(N\) より大きい値）とする。

• クエリ数が最大 \(2 \times 10^5\) と多いので、前計算した累積和テーブルで定数時間応答する。

• 入力の高速読み込み（sys.stdin.buffer.read()）を使用し、Python でも TLE を回避する。

  ソースコード

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
    Q = int(input_data[idx]); idx += 1
    
    # adjacency list
    adj = [[] for _ in range(N)]
    for i in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        adj[u].append(v)
    
    # For each starting node S, we need to find the minimum step at which each node
    # is first reached. But the propagation rule is BFS-like but with a twist:
    # only nodes reached at step t-1 propagate at step t.
    # This is actually exactly BFS on the directed graph!
    # Because in BFS, each node is visited exactly once, and it propagates only once
    # (when it's first discovered). The "set A_t" in the problem corresponds to
    # the BFS frontier at distance t.
    #
    # Wait, but the problem says a node CAN appear in A_t multiple times (at different steps).
    # However, for the purpose of "first time reached", we only care about the minimum t.
    # 
    # Actually, let me re-read. A_t is defined purely based on A_{t-1}, not on "unvisited" nodes.
    # So A_t can contain nodes already visited. This is NOT standard BFS.
    #
    # Example: 1->2, 2->1, 1->3. Start S=1.
    # A_0 = {1}, A_1 = {2,3}, A_2 = {1} (from 2->1), A_3 = {2,3}, ...
    # Node 3 is first reached at step 1. That's fine.
    # But node 1 is in A_0 and A_2. Node 2 is in A_1 and A_3.
    #
    # For the "first time" each node is reached, we want min T_i for each i.
    # The first time a node v is reached is the shortest path distance from S to v 
    # in the directed graph. Because: A_0 = {S}. A_1 = out-neighbors of S. 
    # A_2 = out-neighbors of A_1. Even though nodes can repeat, the first occurrence
    # of any node v is at the shortest path distance from S to v.
    #
    # So for each S, the minimum step at which node v is reached = shortest directed 
    # distance from S to v (infinity if unreachable).
    #
    # For query K: S is valid iff max over all v of dist(S,v) <= K.
    # i.e., all nodes are reachable from S within K steps.
    
    # For each S, compute BFS shortest distances, find max distance (or infinity if some unreachable)
    # Then for query K, count how many S have max_dist[S] <= K.
    
    # N <= 2000, M <= 5000, so N BFS operations: O(N*(N+M)) = O(2000*7000) = 14M, fine.
    
    max_dist = [0] * N  # max_dist[s] = max shortest distance from s to any node
    
    for s in range(N):
        dist = [-1] * N
        dist[s] = 0
        queue = deque([s])
        max_d = 0
        reached = 1
        while queue:
            u = queue.popleft()
            d = dist[u]
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = d + 1
                    if dist[v] > max_d:
                        max_d = dist[v]
                    reached += 1
                    queue.append(v)
        if reached < N:
            max_dist[s] = N + 1  # unreachable, effectively infinity
        else:
            max_dist[s] = max_d
    
    # Precompute answer for each K from 0 to N
    # ans[k] = number of S with max_dist[S] <= k
    count = [0] * (N + 2)
    for s in range(N):
        md = max_dist[s]
        if md <= N:
            count[md] += 1
    
    # prefix sum
    ans = [0] * (N + 1)
    ans[0] = count[0]
    for k in range(1, N + 1):
        ans[k] = ans[k - 1] + count[k]
    
    out = []
    for _ in range(Q):
        K = int(input_data[idx]); idx += 1
        out.append(str(ans[K]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

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