Shirotsume の日記

嘘Greedyを生やすな

Tenka1 Programmer Contest D 「Crossing」

解説などをみるとかなり非直感的な解法があったが,グラフで解釈するといい感じになることに気づいた.

atcoder.jp

問題文要約

整数 N が与えられる.1 以上 N 以下の整数の集合の組 (S_1, S_2, … S_k) (kは自由に決められる)であって,

  • 各iについて,iはk個の集合のうちちょうど2個に含まれる.
  • 任意の2つの集合について,共通要素はちょうど1つである.

条件を満たすものを構築せよ.

解法

集合を頂点,整数を辺に対応させると,以下の条件を満たすk頂点グラフを求める問題になる.

  • それぞれの辺は,ちょうど2個の頂点を結ぶ.
  • 任意の二つの頂点は辺で結ばれている.

これは完全グラフそのものである.よって,以下のように解ける.

  1. k頂点完全グラフの辺数がNとなるようなkを見つける.
  2. k頂点完全グラフの辺に1からNの番号を付ける.辺iの両端点をx, yとするとき,S_x, S_y に iを含める.

atcoder.jp