競プロ文脈でのGale–Ryser theorem
本記事はAcompany😎 Advent Calendar 2025 - Adventarのpart2 5日目の記事となります．
part1はこちら：Acompany😎 Advent Calendar 2025 - Adventar
注：ほとんどは私が執筆したものではないです
目次
Gale–Ryser theorem
緩和Gale–Ryser theorem
問題に適用する上で少し不便な部分があるため，条件を少し緩和したGale–Ryser theoremを扱う．
証明は記事下部で記す．
問題例
ABC143-F Distinct Numbers
問題文要約
$N$ 枚のカードがあり，$i$ 枚目には整数 $A_i$ が書かれている．
$T=1,\cdots,N$ について，次の操作を最大で何回行えるかを求めよ
- 値が互いに異なるカードをちょうど $T$ 枚選んで取り除く
(便宜上変数を$K$から$T$に変更している)
解説
整数 $x$ が書かれたカードが $c_x$ 枚あるとして$C=(c_1,\cdots,c_{|C|})$を定義する．ただし，$|C|=\max{A}$ とする．
$T=t$の時の答えが $ M $ 以上であるとは次の事実を表す．
- \( U(|U| = M) \) の各頂点の次数がそれぞれ $ (t,\cdots, t) $，\( V \) の各頂点の次数が それぞれ$ (c_1, \ldots, c_{|C|})$ 以下となるような単純二部グラフ \( G = (U, V, E) \) が存在する
これは先に記した緩和Gale–Ryser theoremそのものである．よって，$T=t$の場合の答えは次を満たす最大の $ M $ となる．
$$\displaystyle
\sum_{i=1}^{k} t \leq \sum_{j=1}^{|C|} \min(c_{j}, k),\ ^\forall k \in \{1, \ldots, M\}
$$
少し変形して，
$$
\begin{align}
t \leq \left\lfloor \frac{\sum_{j=1}^{|C|} \min(c_{j}, k)}{k} \right\rfloor,\ ^\forall k \in \{1, \ldots, M\}
\end{align}
$$
ここで，右辺は $ t, M $ によらず一定であることから各 $k$ について前計算可能である．愚直に計算すると $O(M|C|)$ かかるが，$k$ を昇順に見て，総和を保持しつつ $\min(c_j,k)$ の値が変わるタイミングだけ着目することで$O(|C| \log{|C|})$で計算できる．
あとは $t=1,...,N$ について，条件を満たす最大の $ M $ を求めれば良い．答えは $t$ の増加に伴って減少していくことから，尺取り法の要領で$O(N+|C|)$で計算できる．
ABC424-G Set list
問題文要約
$N$ 個のボールがあり，ボール $i$ は $a_i$ 個ある．各ボールは区別可能である．
$ M $ 個の箱があり，箱 $j$ に異なるボールを $b_j$ 個入れるとコスト $c_j$ が得られる．
得られるコストの最大値を求めよ．
解説
$b$ は降順でソートしてあるものとする．
まず，使用する箱を $S =\{ s_1,\cdots,{s_{|S|}}\}$ として固定したとき，その箱全てにボールを入れることが可能かを考える．これは次の問題と等価である．
- $U$ の各頂点の次数がそれぞれ $ (b_{s_1}, \ldots, b_{s_{|S|}})$，$V$ の各頂点の次数がそれぞれ $ (a_1,\cdots, a_N) $以下であるような単純二部グラフ \( G = (U, V, E) \) が存在する
これは先に記した緩和Gale–Ryser theoremそのものである．よって，次を満たすことが必要十分である．
$$\displaystyle
\sum_{i=1}^{k} b_{s_i} \leq \sum_{j=1}^{N} \min(a_{j}, k),\ ^\forall k \in \{1, \ldots, |S|\}
$$
これを前提として次のDPを考える．
$$
\begin{aligned}
\textrm{DP}[i][j][k] := &i \textrm{箱目までのうち，} \\
&j \textrm{個を使用していて}，\\
&\textrm{使用したボール数(条件式の左辺)が} k \textrm{の時のスコアの最大値}
\end{aligned}
$$
条件式の右辺は事前に計算しておくものとし，条件式が満たす時に限り$\textrm{DP}[i][j][k] = \max(\textrm{DP}[i-1][j][k], \textrm{DP}[i-1][j-1][k-b_i] + c_i)$ と推移すれば良い．答えは $ \displaystyle \max_{0 \leq j \leq M}\max_{0 \leq k \leq NM} \textrm{DP}[M][j][k]$である．
以上により，状態数$O(NM^3)$，遷移$O(1)$の$O(NM^3)$で解くことができた．
証明
以下の緩和Gale–Ryser theoremを示す．
証明はいくつか考えられるが，ここではGaleによる証明[1]をベースとしたものを記す．他にもRyserによる証明[2]や帰納法を用いた証明などがあるが，本記事では扱わない．
条件の言い換え
以下の頂点と辺を持つフローネットワーク $N$ を構築する．
頂点
- 始点 $s$
- 終点 $t$
- 左側頂点集合 $U = \{u_1, \dots, u_n\}$
- 右側頂点集合 $V = \{v_1, \dots, v_m\}$
辺
- $s \to u_i$: 容量 $a_i \quad (1 \le i \le n)$
- $v_j \to t$: 容量 $b_j \quad (1 \le j \le m)$
- $u_i \to v_j$: 容量 $1 \quad (1 \le i \le n, \ 1 \le j \le m)$
「このネットワークにおいて最大のs-tフローが $\sum a_i$ 以上である」ことと「条件を満たす二部グラフが存在すること」は同値である．さらに，最大流最小カット定理より最大のs-tフローと最小のs-tカットが等しいため，結局 最小の$s-t$ カット $(S, T) (s \in S, t \in T)$ について，次の不等式が成り立つ．
$$
\displaystyle \min_{(S, T)} C(S, T) \ge \sum_{i=1}^n a_i \tag{1}
$$
最小カット値の計算
あるカット$(S,T)$について，各頂点が$S$に含まれるかどうか次の集合を定義する．
$$
\displaystyle
\begin{aligned}
U_S = U \cap S, V_S = V \cap S
\end{aligned}
$$
すると，カット容量 $C(S, T)$ は以下の3つの和となる．
- $\displaystyle \sum_{u_i \notin U_S} a_i$：$T$ 側に属する $u_i$ へ向かう辺 $s \to u_i$ の容量和
- $\displaystyle \sum_{v_j \in V_S} b_j$：$S$ 側に属する $v_j$ から出る辺 $v_j \to t$ の容量和
- $\displaystyle \sum_{v_j \notin V_S} |U_S|$：$S$ 側に属する$|U_S|$個の頂点 $u_i$ から，$T$ 側に属する $v_j$ へ向かう辺 $u_i \to v_j$ の容量和
よって，最小カットは次で表せる．
$$
\begin{aligned}
\min_{(S,T)} C(S,T) &= \min_{(U_S, V_S)} \left( \sum_{u_i \notin U_S} a_i + \sum_{v_j \in V_S} b_j + \sum_{v_j \notin V_S} |U_S| \right)
\end{aligned}
$$
さらに変形して，
$$
\begin{aligned}
\min_{(U_S, V_S)} \left( \sum_{u_i \notin U_S} a_i + \sum_{v_j \in V_S} b_j + \sum_{v_j \notin V_S} |U_S| \right)
&= \min_{U_S} \min_{V_S} \left( \sum_{u_i \notin U_S} a_i + \sum_{v_j \in V_S} b_j + \sum_{v_j \notin V_S} |U_S| \right) \\
&= \min_{U_S} \left( \sum_{u_i \notin U_S} a_i + \min_{V_S} \left( \sum_{v_j \in V_S} b_j + \sum_{v_j \notin V_S} |U_S| \right) \right) \\
&= \min_{U_S} \left( \sum_{u_i \notin U_S} a_i + \sum_{j} \min \left( b_j, |U_S| \right) \right) \\
&= \min_{k} \min_{|U_S|=k} \left( \sum_{u_i \notin U_S} a_i + \sum_{j} \min (b_j, k) \right) \\
&= \min_{k} \left( \sum_{i > k} a_i + \sum_{j} \min (b_j, k) \right)
\end{aligned}
$$
よって，
$$
\min_{(S,T)} C(S,T) = \min_{k} \left( \sum_{i > k} a_i + \sum_{j} \min (b_j, k) \right) \tag{2}
$$
結論
式(1)，式(2)より，次の不等式が成り立つことが，
$$
\sum_{i=1}^n a_i \leq \min_{k} \left( \sum_{i > k} a_i + \sum_{j} \min (b_j, k) \right)
$$
さらに，任意の $k$ について成り立つと解釈することで，
$$
\begin{aligned}
& \sum_{i=1}^n a_i \leq \min_{k} \left( \sum_{i > k} a_i + \sum_{j} \min (b_j, k) \right) \\
\iff& \sum_{i=1}^n a_i \leq \sum_{i > k} a_i + \sum_{j} \min (b_j, k), \ ^\forall k \in \{1, \ldots, n\}\\
\iff& \sum_{i=1}^k a_i \leq \sum_{j=1}^{m} \min (b_j, k), \ ^\forall k \in \{1, \ldots, n\}
\end{aligned}
$$
以上により示せた．
参考文献
- [1] D. Gale, “A theorem on flows in networks,” Pacific Journal of Mathematics, 7(2), 1073–1082, 1957. https://msp.org/pjm/1957/7-2/p04.xhtml
- [2] Ryser HJ. Combinatorial Properties of Matrices of Zeros and Ones. Canadian Journal of Mathematics. 1957;9:371-377. doi:10.4153/CJM-1957-044-3
