問題概要

正の整数からなる長さ $N$ の数列 $a_{1}, a_{2}, \dots, a_{N}$ が与えられる。

以下の条件を満たすような、頂点数 $N$ のグラフが存在するかどうかを判定せよ。

単純グラフである
頂点 $i$ の次数が $a_{i}$ である

制約

$1 \le N \le 2 \times 10^{5}$
$\sum_{i=1}^{N} a_{i} \le 10^{5}$

考えたこと

頂点次数の制約を満たすグラフが存在するかどうかを判定するには、よく知られた Greedy 解法がある。

以下を繰り返す

残っている頂点のうち、次数最大の頂点 $v$ を求める (次数を $d$ とする)
残っている頂点と頂点を除いた頂点のうち、次数が大きい順に個選ぶ ( とする)
- このとき、次数 1 以上の頂点が $d$ 個未満の場合は "No"
頂点 $v$ と各頂点 $u_{1}, \dots, u_{d}$ を結んでいく
頂点 $v$ を確定済みとして、以降、残りの頂点のみを考える

この解法は愚直に実装すると $O(N^{2} \log N)$ の計算量となってしまう。しかし、 $a_{i}$ の総和を $S$ として $S \le 2 \times 10^{5}$ であることに着目して高速化できる。

高速化

上記解法における「残っている頂点の次数たち」を priority_queue で管理する。残っている頂点のうち、次数最大の頂点 $v$ は $O(\log N)$ の計算量で取り出せる。続いて、 priority_queue から先頭から $d$ 個の値を取り出していき、それらから 1 を引いて、再度 priority_queue に挿入していけばよい。

一連の操作を通して、priority_queue に要素を挿入したり削除したりする回数は $O(S)$ であるから、全体の計算量は $O(N + S \log N)$ と評価できる。

コード

#include <bits/stdc++.h>
using namespace std;

bool solve() {
    // 入力
    int N;
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    
    // 残っている頂点の次数を管理する priority queue
    priority_queue<int> que;
    for (int i = 0; i < N; ++i) que.push(a[i]);
    
    while (!que.empty()) {
        // 残っている頂点のうち、次数最大の頂点を取り出す
        int d = que.top();
        que.pop();
        
        // 残っている頂点のうち、次数が大きい順に d 個の頂点を取り出して次数を 1 ずつ引く
        vector<int> tmp;
        for (int i = 0; i < d; ++i) {
            if (que.empty()) return false;
            int v = que.top();
            que.pop();
            if (v == 0) return false;
            if (v - 1 > 0) tmp.push_back(v - 1);
        }
        
        // それらの頂点を再度 priority queue に挿入する
        for (auto v : tmp) que.push(v);
    }
    return true;
}

int main() {
    cout << (solve() ? "Yes" : "No") << endl;
}