解説などをみるとかなり非直感的な解法があったが,グラフで解釈するといい感じになることに気づいた.
問題文要約
整数 N が与えられる.1 以上 N 以下の整数の集合の組 (S_1, S_2, … S_k) (kは自由に決められる)であって,
- 各iについて,iはk個の集合のうちちょうど2個に含まれる.
- 任意の2つの集合について,共通要素はちょうど1つである.
条件を満たすものを構築せよ.
解法
集合を頂点,整数を辺に対応させると,以下の条件を満たすk頂点グラフを求める問題になる.
- それぞれの辺は,ちょうど2個の頂点を結ぶ.
- 任意の二つの頂点は辺で結ばれている.
これは完全グラフそのものである.よって,以下のように解ける.
- k頂点完全グラフの辺数がNとなるようなkを見つける.
- k頂点完全グラフの辺に1からNの番号を付ける.辺iの両端点をx, yとするとき,S_x, S_y に iを含める.