みんなのプロコン本戦B チーム決め

ある命題が成立する最小値xについて、任意のx’≧xについて同様に成立するときの最小値を求めよという問題であれば、からなず二分探索をするべき。

これもまずチーム間の実力差の最小値kを仮定して矛盾があるかどうかで二分探索を行う。例えばxがとても大きいとき、常にチーム編成は可能である。

あとはxが仮定されたときにチーム編成が可能であるかどうかを確認する。A、Bともにソートして小さい方から実力差x以内の参加者を貪欲に確保していく。ここでも二分探索を用いることでO(A log(B))に計算量を抑えることが可能。

というわけで全体の計算量はO(A log(B) log(x_max)))で間に合う(A, B≦10^6)

アルゴリズム忘備録