AtCoder Beginner Contest 227 D 問題 Project Planning
問題
提出解答
問題の概要
個の部署からなる会社があり,
番目の部署の人数は
である.
以下を満たす 人からなるグループをいくつか作るとき, そのグループの数の最大値を求めよ.
- どのグループにおいても,
人の属する部署は全部異なる.
- 同じ人は2つ以上のグループに属さない.
制約
解法
個のグループを作れることと, 以下は同値である.
- 十分条件
各部署に対して,
個のグループのどれかに参加している人は
人である. また,
人のグループが
個あるので, 不等式が成り立つ.
- 必要条件
のときは明らかである.
のとき,
とする. 列
を
とし, に対して, 部署
の人をグループ
に属させるとする. すると,
個のグループ
ができ, 同じ整数は連続して高々
個しかでないので, 同じグループに属することはない. よって, これが条件を満たすグループの作成の例である.
よって, 問題は を満たす最大の
を求めることになる. ここで, この条件は同値な元条件を考えることにより, 単調減少であることがわかる. よって, 二分探索によって高速に最大の
を求めることができる.
二分探索の明らかな下界は , 上界は
であり, 計算量
で求めることができる.