問題
$N$ 個のアイテム（番号 $1$ 〜 $N$）と、$M$ 個の集合 $S_1, \dots, S_M$（それぞれ $\{1,\dots,N\}$ の部分集合）が与えられる。
これらの集合の中からいくつかを選び、選んだ集合の和集合がちょうど $\{1,\dots,N\}$ に一致し、かつどの2つの選んだ集合も互いに素（各アイテムがちょうど1回だけ選ばれた集合に含まれる）になるようにしたい。そのような選び方が存在するか判定し、存在するなら選んだ集合の番号を1つ出力せよ。存在しなければ -1 を出力せよ。
入力形式
N M
K_1 a_1 ... a_{K_1}
K_2 a_1 ... a_{K_2}
...
K_M a_1 ... a_{K_M}制約
入出力例
入力例1
4 4
2 1 2
2 3 4
2 1 3
2 2 4出力例1
1 2集合1 {1,2} と集合2 {3,4} を選ぶと {1,2,3,4} をちょうど1回ずつ被覆できる。「3 4」も正解
入力例2
3 2
2 1 2
2 2 3出力例2
-1アイテム2を含む集合しかなく、両方選ぶと重複、片方だけでは被覆漏れが出るため不可能
概念図
ヒント（段階的開示）
ヒント1（方向性）
すべての部分集合 $2^M$ 通りを全探索すると $M \le 200$ では到底間に合わない。バックトラック（分岐限定法）で「まだ被覆されていないアイテムのうち1つを選び、それを含む集合のどれかを選ぶ」という探索木を作ると、枝刈りの効きが良い探索になる。この探索を効率よく実装するデータ構造として、Donald Knuth の Dancing Links (DLX) を考える。
ヒント2（アプローチ）
DLXは「行＝集合」「列＝アイテム」の0-1行列を、各セルが上下左右の隣接する1同士を指す双方向連結リストとして表現する。ある列（アイテム）を選択して被覆すると、その列に1を持つ全ての行を「削除」し、それらの行が1を持つ他の列からもそれらの行を取り除く。この削除は連結リストの unlink 操作なので $O(1)$ で行え、バックトラック時は逆順に unlink した順序を辿って relink するだけで完全に元に戻せる。
ヒント3（誘導）
$N \le 20, M \le 200$ の制約であればビットマスクで「まだ被覆されていない列集合」を管理し、各列を選ぶ代わりに「残っている行の中から、その行が持つ列がすべて未被覆であるものを選んで被覆マスクを更新し再帰」するだけでも十分高速に動く（本質はDLXと同じ分岐限定法）。
def search(covered, chosen):
if covered == full_mask:
return chosen
target = (~covered & full_mask) & (-(~covered & full_mask))
for i, mask in enumerate(row_masks):
if mask & target and (mask & covered) == 0:
res = search(covered | mask, chosen + [i])
if res is not None:
return res
return None模範解答 (Python)
import sys
def solve():
input_data = sys.stdin.read().split()
idx = 0
n = int(input_data[idx]); idx += 1
m = int(input_data[idx]); idx += 1
row_masks = []
for _ in range(m):
k = int(input_data[idx]); idx += 1
mask = 0
for _ in range(k):
a = int(input_data[idx]); idx += 1
mask |= (1 << (a - 1))
row_masks.append(mask)
full_mask = (1 << n) - 1
rows_by_item = [[] for _ in range(n)]
for i, mask in enumerate(row_masks):
for b in range(n):
if mask & (1 << b):
rows_by_item[b].append(i)
chosen_stack = []
sys.setrecursionlimit(10000)
def search(covered):
if covered == full_mask:
return True
rest = (~covered) & full_mask
best_item = -1
best_count = None
b = 0
tmp = rest
while tmp:
if tmp & 1:
cnt = sum(1 for r in rows_by_item[b] if (row_masks[r] & covered) == 0)
if best_count is None or cnt < best_count:
best_count = cnt
best_item = b
if cnt == 0:
return False
tmp >>= 1
b += 1
for r in rows_by_item[best_item]:
if row_masks[r] & covered:
continue
chosen_stack.append(r)
if search(covered | row_masks[r]):
return True
chosen_stack.pop()
return False
if search(0):
print(' '.join(str(r + 1) for r in sorted(chosen_stack)))
else:
print(-1)
solve()Step-by-Step 解説
$M$個の集合から「和が $\{1,\dots,N\}$ に一致し重複なし」の部分集合族を選ぶ問題は、0-1行列（行＝集合、列＝アイテム）における Exact Cover Problem そのものである。Knuth の Algorithm X はこれを再帰的に解く汎用アルゴリズムであり、DLX はその実装を高速化するデータ構造。
毎回「まだ被覆されておらず、かつそれを被覆できる残り行数が最も少ないアイテム」を選んで分岐する。これにより分岐数が最小化され、探索木が大きく枝刈りされる。
選んだアイテムを被覆できる行を1つずつ試し、その行を選んだ場合の新しい被覆状態で再帰する。本来のDLX実装ではこれを連結リストのunlink/relinkで $O(1)$ に行うが、$N\le20$ の本問題ではビットマスク演算で同等の効果が得られる。
chosen_stack に追加した行が失敗に終わった場合は必ず pop() して状態を戻す。この対称性（push/pop, unlink/relink）を崩すと探索状態が壊れる。最悪ケースは指数時間だが、MRVヒューリスティックにより実用的な入力では劇的に枝刈りされ、本問題の制約では十分高速に動作する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 全部分集合 $2^M$ を素朴に全探索 | 制約 $M\le200$ を見落とす | アイテム側（$N\le20$）を軸にMRV分岐する |
| 列選択を常に固定順にする | ヒューリスティックの効果を軽視 | 残り候補行数最小のアイテムを毎回選び直す |
バックトラック時に chosen_stack.pop() を忘れる | 再帰の失敗パスで状態復元を省略 | 各再帰呼び出しの前後でpush/popを必ず対にする |
| 行が空集合被覆にも使えると誤解 | 空行を許容してしまう | $K_i \ge 1$ の制約を前提に実装する |
次のステップ
- 発展: 各行に「重み」を付け、被覆にかかる総コストを最小化する重み付き厳密被覆問題（分岐限定法に下界を加える）
- 次回予告: モノトニックキュー最適化DP（Monotonic Deque Optimization・スライディングウィンドウ最大値によるDP高速化）