天下一プログラマーコンテスト 2018 D - Crossing

• 問題
• AC

集合が$k$個ある時、$S_1 \cap S_2, ..., S_1 \cap S_k$はそれぞれ異なっていなければならないので、$|S_1| \ge k-1$である。また$|S_1| \ge k$と仮定すると、$S_1$は$S_1 \cap S_2, ..., S_1 \cap S_k$に含まれない整数を少なくとも１つ含むことになり、それを$p$とすると$p$は問題文の条件1により$S_2, ..., S_k$のいずれかに含まれることになって条件2に反する。従って、$|S_1|=k-1$である。同じことが任意の$S_i$について成り立つ: $|S_i|=k-1$。

ところで、条件1により$k(k-1)=|S_1|+...+|S_k|=2N$でなければならないので、$k^2-k-2N=0$。したがって$k=(1+\sqrt{1+8N})/2$。
これが整数であることが必要条件である。逆に、整数であれば適当に構成すればつじつまが合うはず。¹

---

1. 解いているときは自明と思ったけど、言うほどでもなかった。Editorialの方法が証明ということになるか。 ↩︎