Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 227 D 問題 Project Planning

AtCoder ABC ABC227 D問題 400 pts

問題

提出解答

問題の概要

$N$ 個の部署からなる会社があり, $i$ 番目の部署の人数は $A_i$ である.

以下を満たす $K$ 人からなるグループをいくつか作るとき, そのグループの数の最大値を求めよ.

どのグループにおいても, $K$ 人の属する部署は全部異なる.
同じ人は2つ以上のグループに属さない.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^{12}$

解法

$X$ 個のグループを作れることと, 以下は同値である.

$\displaystyle \sum_{i=1}^N \min(X,A_i) \geq KX$

十分条件
各部署 $i$ に対して, $X$ 個のグループのどれかに参加している人は $\min(X, A_i)$ 人である. また, $K$ 人のグループが $X$ 個あるので, 不等式が成り立つ.
必要条件
$X=0$ のときは明らかである. $X \geq 1$ のとき, $B_i:=\min(X, A_i)$ とする. 列 $C$ を

$C=(\underbrace{1,\dots,1}_{B_1}, \underbrace{2, \dots,2}_{B_2}, \dots, \underbrace{N, \dots, N}_{B_N})$

とし, $1 \leq j \leq KX (\leq |C|)$ に対して, 部署 $C_j$ の人をグループ $j \pmod{X}$ に属させるとする. すると, $K$ 個のグループ $0,1, \dots, X-1$ ができ, 同じ整数は連続して高々 $X$ 個しかでないので, 同じグループに属することはない. よって, これが条件を満たすグループの作成の例である.

よって, 問題は $\displaystyle \sum_{i=1}^N \min(X,A_i) \geq KX$ を満たす最大の $X$ を求めることになる. ここで, この条件は同値な元条件を考えることにより, 単調減少であることがわかる. よって, 二分探索によって高速に最大の $X$ を求めることができる.

二分探索の明らかな下界は $0$ , 上界は $\displaystyle \dfrac{1}{K} \sum_{i=1}^N A_i$ であり, 計算量 $\displaystyle O\left(N+\log \sum_{i=1}^N A_i \right)$ で求めることができる.