概要

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

考察

1. 噂の伝播をグラフとして捉える

生徒を「頂点」、噂の伝達関係を「有向辺」とする有向グラフを考えます。 「生徒 \(u\) が噂を受け取った次のステップで生徒 \(v\) に噂が伝わる」というルールは、グラフ上を 1ステップで1辺進む ことに対応します。

最初に生徒 \(S\) が噂を受け取ったとき、各生徒 \(i\) が初めて噂を受け取るステップは、頂点 \(S\) から頂点 \(i\) への最短経路の長さ（最短ステップ数）に等しくなります。

したがって、「ステップ \(0\) からステップ \(K\) までの間に、すべての生徒が少なくとも \(1\) 回は噂を受け取る」という条件は、グラフの言葉で以下のように言い換えられます。

• 「始点 \(S\) からすべての頂点への最短距離が、すべて \(K\) 以下である」

これはさらに、以下と同値です。

• 「始点 \(S\) からすべての頂点に到達可能であり、かつ \(S\) から最も遠い頂点への最短距離が \(K\) 以下である」

2. 素朴なアプローチとその限界

クエリごとに「始点 \(S\) をすべて試して、そこから \(K\) ステップ以内に全員に伝わるか」を判定しようとすると、1回の判定に幅優先探索（BFS）で \(O(N + M)\) かかります。 これをすべての \(S\) （\(N\) 個）について行い、さらに \(Q\) 個のクエリすべてで繰り返すと、全体の計算量は \(O(Q \cdot N(N + M))\) となり、実行時間制限に間に合いません（TLEとなります）。

3. 効率的な解決策：前計算と累積和

クエリ \(K\) に依存しない部分を事前に計算しておくことで、各クエリに高速に答えられるようにします。

1. 各頂点 \(S\) (\(1 \leq S \leq N\)) を始点としてBFSを行い、以下の2つの情報を求めます。
   • \(S\) から到達できる頂点数
   • \(S\) から到達できる頂点への最短距離の最大値（これを \(D_S\) とします）
2. もし \(S\) からすべての頂点に到達できる（到達できる頂点数が \(N\) である）なら、その \(D_S\) を記録します。全員に到達できない場合は、いくらステップが進んでも全員に噂は伝わらないため、無視します。
3. 最短距離の最大値がちょうど \(d\) となるような始点 \(S\) の個数を count_D[d] とします。
4. count_D の累積和 pref を計算します。pref[k] は「最短距離の最大値が \(k\) 以下であるような始点 \(S\) の個数」を表します。

このように前計算をしておけば、各クエリ \(K_j\) に対しては pref[K_j] を参照するだけで \(O(1)\) で回答できる ようになります。

---

アルゴリズム

1. グラフの構築: 与えられた伝達関係から、隣接リスト adj を作成します。

2. 各始点からのBFS: 各 \(S \in [1, N]\) について、以下を行います。

   • キューを用いたBFSにより、始点 \(S\) から各頂点への最短距離を求めます。
   • 到達した頂点数 visited_count と、その時の最短距離の最大値 max_dist を更新していきます。
   • BFS終了後、visited_count == N であれば、count_D[max_dist] を \(1\) 増やします。

3. 累積和の計算: 配列 pref を以下のように構築します。

   • pref[0] = count_D[0]
   • pref[i] = pref[i-1] + count_D[i] （\(1 \leq i \leq N\)）

4. クエリへの回答: 各クエリ \(K_j\) について、以下を出力します。

   • \(K_j > N\) の場合は、最大距離は高々 \(N\) なので \(K_j = N\) とみなします。
   • pref[K_j] を出力します。

---

計算量

時間計算量

• BFSによる前計算: 1回のBFSにかかる時間は \(O(N + M)\) です。これを \(N\) 回行うため、全体で \(O(N(N + M))\) となります。
• 累積和の計算: 長さ \(N\) の配列の累積和をとるため \(O(N)\) です。
• クエリ処理: \(Q\) 個のクエリに対してそれぞれ \(O(1)\) で答えるため、全体で \(O(Q)\) です。

総時間計算量は \(O(N(N + M) + Q)\) となります。 制約の \(N \leq 2000, M \leq 50000\) において、 \(N(N+M) \approx 1.04 \times 10^8\) 回の計算量となり、C++では 1 秒以内に十分実行可能です。

空間計算量

• グラフの隣接リストの保持に \(O(N + M)\)。
• BFS用の各種配列（距離、訪問フラグなど）に \(O(N)\)。

総空間計算量は \(O(N + M)\) となり、メモリ制限に対しても非常に軽量です。

---

実装のポイント

• 訪問フラグの初期化の高速化: 各 \(S\) のループで毎回 vis 配列を 0 で初期化すると、それだけで \(O(N^2)\) の時間がかかってしまいます。 正解コードでは、vis_id という変数を用意し、各ループで vis_id++ を行い、vis[v] == vis_id かどうかで訪問済みかを判定しています。これにより、配列の初期化を不要にし、定数倍の高速化を実現しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M, Q;
    if (!(cin >> N >> M >> Q)) return 0;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> dist(N + 1, -1);
    vector<int> vis(N + 1, 0);
    int vis_id = 0;

    vector<int> count_D(N + 1, 0);
    vector<int> q(N + 1);

    // 各頂点 S を始点とする BFS
    for (int S = 1; S <= N; ++S) {
        vis_id++;
        dist[S] = 0;
        vis[S] = vis_id;
        int q_head = 0, q_tail = 0;
        q[q_tail++] = S;

        int visited_count = 0;
        int max_dist = 0;

        while (q_head < q_tail) {
            int u = q[q_head++];
            visited_count++;
            max_dist = max(max_dist, dist[u]);
            for (int v : adj[u]) {
                if (vis[v] != vis_id) {
                    vis[v] = vis_id;
                    dist[v] = dist[u] + 1;
                    q[q_tail++] = v;
                }
            }
        }

        // すべての頂点に到達可能な場合のみカウント
        if (visited_count == N) {
            if (max_dist <= N) {
                count_D[max_dist]++;
            }
        }
    }

    // 累積和を計算
    vector<int> pref(N + 1, 0);
    pref[0] = count_D[0];
    for (int i = 1; i <= N; ++i) {
        pref[i] = pref[i - 1] + count_D[i];
    }

    // クエリ処理
    for (int j = 0; j < Q; ++j) {
        int K;
        cin >> K;
        if (K > N) K = N;
        cout << pref[K] << "\n";
    }

    return 0;
}

---

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