3024

N人の人が、M人ずつG個のグループに分かれている。一人の人は必ず二つのグループに属しているが、同じ二つのグループに属していることはなく、任意の二つのグループについて両方に属している人が一人いる。Nが与えられるので、このようなMとGが存在するかどうかを答えよ、という問題。

あるグループについて考えると、M人がそれぞれ別のグループに属していると同時に、これらM個のグループの他にグループがあると、そのグループとの共通のメンバーがいなくなるので、G=M+1になる。N人が2個のグループに属している事実と、M人のグループがG個あるという事実から、N*2=M*Gが成り立つ。以上を整理すると、N*2=M*(M+1)であり、これを満たすMがあるかどうかを二分探索すればおしまい。