【AtCoder】ABC 442 C - Peer Review

2026-01-252026-01-26

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 174 / NoviSteps: 4Q / 配点: 300 点

問題概要

$N$ 人の研究者がおり、 $i = 1, 2, \ldots, M$ に対して研究者 $A_i$ と研究者 $B_i$ は互いに利害関係にある。論文の査読者は、その論文の著者とは異なり、著者と利害関係にない相異なる $3$ 人の研究者でなければならない。

$i = 1, 2, \ldots, N$ について以下の問題を解け。

研究者 $i$ が著者である論文の査読者の $3$ 人組として考えられるものは何通りあるか求めよ。ただし、すべての論文は単著であるものとする。

制約

$1 \leq N, M \leq 2 \times 10^5$
$A_i \neq B_i$
入力される値はすべて整数

考察

研究者間の利害関係のグラフを考えたとき、研究者 $i$ 自身とその隣接頂点を除いた人から $3$ 人を選ぶ組み合わせの数を求めればよい。

頂点 $i$ の次数を $d_i$ とすると、求める組み合わせの数は二項係数 $\displaystyle \binom{N - 1 - d_i}{3}$ である。

実装例

nCk関数は自作のものを使っている。

$d_i < 3$ のときは計算できないので $0$ を出力すること。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.using ll = long long;
7. 
8.ll nCk(ll n, ll r)
9.{
10.    if (r < 0 || n < r)
11.        return 0;
12.    ll ans = 1;
13.    for (ll i = 1; i <= r; i++)
14.    {
15.        ans *= n--;
16.        ans /= i;
17.    }
18.    return ans;
19.}
20. 
21.// ======================================== //
22. 
23.int main()
24.{
25.    int N, M;
26.    cin >> N >> M;
27.    vector<int> degs(N, 0);
28.    rep(i, 0, M)
29.    {
30.        int A, B;
31.        cin >> A >> B;
32.        A--;
33.        B--;
34.        degs[A]++;
35.        degs[B]++;
36.    }
37. 
38.    rep(i, 0, N)
39.    {
40.        ll x = N - 1 - degs[i];
41.        if (x < 3)
42.            cout << 0 << endl;
43.        else
44.            cout << nCk(x, 3) << endl;
45.    }
46. 
47.    return 0;
48.}