Day 097-Q2 | Gale-Ryser定理

問題

左側頂点集合 $L=\{1,\dots,N\}$、右側頂点集合 $R=\{1,\dots,M\}$ を持つ二部グラフを考える。左側頂点の次数列 $d_1,\dots,d_N$ と右側頂点の次数列 $e_1,\dots,e_M$ が与えられたとき、多重辺を持たない単純な二部グラフであって、頂点 $i\in L$ の次数がちょうど $d_i$、頂点 $j\in R$ の次数がちょうど $e_j$ となるものが存在するか判定せよ。

入力形式

N M
d_1 d_2 ... d_N
e_1 e_2 ... e_M

制約

$1 \le N, M \le 2\times10^5$

$0 \le d_i \le M$

$0 \le e_j \le N$

入出力例

入力例1

3 3
2 2 2
2 2 2

出力例1

Yes

各頂点が自分以外の相手2頂点すべてと1本ずつ辺を持つグラフ（$K_{3,3}$ から完全マッチングを1つ除いたグラフ）が条件を満たす。

入力例2

2 2
3 1
2 2

出力例2

No

左頂点1が次数3を持つには右側頂点3個以上と辺を持つ必要があるが、右側頂点は2個しかないため実現不可能。

概念図

ヒント（段階的開示）

ヒント1: 方向性

次数の合計が両側で一致することは必要条件だが、それだけでは不十分である。「次数の大きい左頂点から順に、右側の次数上限を使い切っていく」貪欲な構成法がいつ破綻するかを考えよ。

ヒント2: アプローチ

Gale-Ryser定理: $d_1\ge\dots\ge d_N$ に降順ソートしておく。単純二部グラフが存在する必要十分条件は $$\sum_{i=1}^{N} d_i = \sum_{j=1}^{M} e_j \quad \text{かつ}\quad \forall k: \sum_{i=1}^{k} d_i \le \sum_{j=1}^{M}\min(e_j,k)$$

ヒント3: 誘導（コード骨格）

import bisect
pos = bisect.bisect_right(e_sorted, k)
rhs = prefix[pos] + k * (M - pos)

e を昇順ソートして累積和を持てば、sum(min(e_j,k) for j) は二分探索で $O(\log M)$ 計算できる。

模範解答 (Python)

import sys
import bisect


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    d = [int(data[idx + i]) for i in range(n)]; idx += n
    e = [int(data[idx + i]) for i in range(m)]; idx += m

    if sum(d) != sum(e):
        print("No")
        return

    d_sorted = sorted(d, reverse=True)
    e_sorted = sorted(e)
    prefix = [0] * (m + 1)
    for i in range(m):
        prefix[i + 1] = prefix[i] + e_sorted[i]

    lhs = 0
    for k in range(1, n + 1):
        lhs += d_sorted[k - 1]
        pos = bisect.bisect_right(e_sorted, k)
        rhs = prefix[pos] + k * (m - pos)
        if lhs > rhs:
            print("No")
            return

    print("Yes")


solve()

計算量: ソート $O(N\log N+M\log M)$、各 $k$ の二分探索 $O(\log M)$。全体 $O((N+M)\log(N+M))$。

Step-by-Step 解説

1合計次数の一致確認
両側の次数合計は総辺数の2倍のカウントなので、一致しなければ即座に No。

2左次数列を降順ソート
「次数の大きい頂点から確認していく」貪欲法の正しさを保証するため。

3各 k について容量制約を確認
上位k頂点の次数合計が、右側の「各頂点が高々k本まで受け入れられる」上限の合計を超えていないか確認。

4全てのkを通過すれば実現可能
Gale-Ryser定理により実現可能なグラフが必ず存在する。

よくあるミス

ミス	原因	正しい書き方
合計次数の一致だけ確認して終わる	十分条件だと誤解	全ての $k=1,\dots,N$ について不等式を確認する
d を降順にソートし忘れる	定理の前提条件を見落とす	`sorted(d, reverse=True)` を必ず行う
Σmin(e_j,k) を毎回O(M)で計算しTLE	二分探索を使わず素朴に計算	e昇順ソート＋累積和＋bisectで O(log M) 化
Havel-Hakimi法と混同する	二部グラフ専用の定理であることを忘れる	二部グラフの次数列判定には必ず Gale-Ryser を使う

次のステップ

発展: 判定だけでなく実際にグラフを構成する貪欲アルゴリズムの実装
発展: 多重辺を許す場合の次数列実現可能性との違いを考察する
次回予告: 区間加算・区間和 BIT（Fenwick Tree ×2 のトリック）

自己評価

完全理解おおむね理解要復習

Day 097-Q2 — Gale-Ryser定理（二部次数列の実現可能性判定）

問題