問題
思考過程
最大ペアをどうにか構築できないかを考えてみようとする。
貪欲に多い部署からK人のペアを作るようにすると、最大ペアは作れなさそう（雑感）。他にうまく構築する方法が思いつかない。
なんとなくこういう、うまく組み合わせられるか考えるのが面倒なタイプの問題は、二分探索で判定問題にするとできるかもしれないので、考えてみる。
つまり、「m組のグループに分けるとき、すべてのグループでK人以上所属できることができるかどうか」という判定を考えてみる。
やっぱり人数が多い部署から、それぞれのグループに割り当てていくことを考える。
m組より人数が多い場合は、すべてのグループに割当させることになる。それ以上割り当てはできない。
m組まで足りない場合、途中のグループまで割り当てる。そのあと、次に考える部署についてはその続きから割り当てていく。このとき、同じグループに同じ部署が入ってしまうようなことが起こらない。なぜなら、続きから割り当てていって、同じグループに同じ部署の人が入ってしまうのは、部署の人数がm人を超えている場合であるが、続きから割り当てているということは、すでにm人を下回っている状況になっている。人数の多い部署から考えることで、同じグループに同じ部署の人が入るような状況にならないのである。
上のやり方であれば、可能な限り最大に割り当てを行えているはず。
ということで、このときのグループの所属人数の最小値を計算し、K以上かどうかで判定する。
グループが作れる最大値は なので、
で解ける。
