https://kntychance.hatenablog.jp/entry/2025/03/24/225629

鳩が $N$ 匹と鳩の巣が $M$ 個あり、各鳩はいずれか一つの巣に入っているとします。このとき、 $\mathbf{N \gt M}$ ならば、必ず $\mathbf{2}$ 匹以上の鳩が入った巣が存在します。あたりまえ体操ですね。この主張を、鳩ノ巣原理と呼びます。

この鳩ノ巣原理、競プロでたまーに出てきては猛威を振るっていくんですが、本記事では昔出てきてちょっと感心した良問を紹介します。

扱う問題はこれ ↓ です

問題概要

$N$ 個の部署があり、各部署 $i ~ (1 \le i \le N)$ には $A_i$ 人の社員が所属している。
人組のプロジェクトを作る。ここで、
- 一つのプロジェクトに同じ部署に所属する社員が $2$ 人以上参加してはならない。
- 一人が $2$ つ以上のプロジェクトに参加してはならない。
最大でいくつのプロジェクトを作ることができるか。

（ $2 \times {10}^{17}$ 人の社員を持つこの社、ヤバすぎる）

単純な解法として、貪欲法が浮かびます。

例えば $K = 3$ として、（必要ならソートをして）部署が人数の昇順に並んでいるとして、

しかし、この解法は次のようなケースで最適解となりません。

（貪欲法だと $1$ 個しかプロジェクトが作れないですね。）

いつものです。

$P(x) := x \text{ 個のプロジェクトを作れる}$ という判定問題を考え、 $P(x) = True$ となる最大の $x$ を二分探索します。

実は、任意の $x$ に対し次が成り立ちます：

\begin{equation} P(x) \Leftrightarrow \sum_{i=1}^{N} \min (A_i, x) \ge Kx \end{equation}

∵ 各部署について $x$ 人を超える分は無視してよいことに注意して（鳩ノ巣原理！）、各部署 $i ~ (1 \le i \le N)$ の社員数を $\min (A_i, x)$ とおきなおしたとき、

$(\Rightarrow)$ : 対偶を考えると、社員総数が足りていないので $P(x) = False$ は明らか。
$(\Leftarrow)$ : プロジェクトをそれぞれ $p_0, p_1, \dots, p_{x-1}$ とする。部署順に社員全員を一列に並べて（同一部署の社員は自由な順で並べてok）前から順に $0, 1, \dots, (Kx-1), \dots$ と番号をつけたとき、各社員 $j ~ (0 \le j \lt Kx)$ を $p_{j \% x}$ に参加させればよい*1。