2019年4月21日日曜日

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

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

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

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


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