Day 090-Q4 — Dancing Links（Algorithm X・厳密被覆問題の数え上げ）

問題

$N$ 個のアイテムと $M$ 個の集合（行）が与えられる。行の集合からいくつか選び、選んだ行たちの表す部分集合が互いに素であり和集合がちょうど全アイテムに一致するようにする（厳密被覆 / exact cover）。このような選び方の総数を求めよ。

入出力例

4 6
2 1 2
2 3 4
2 1 3
2 2 4
4 1 2 3 4
2 2 3

3

2 3
1 1
1 2
2 1 2

2

例1: {行1+行2}, {行3+行4}, {行5単独}の3通り。行6を含む組は残り{1,4}を覆う行がなく不成立。

概念図: 疎行列を双方向連結リストで表現

ヒント

def cover(c):
    right[left[c]] = right[c]; left[right[c]] = left[c]
    i = down[c]
    while i != c:
        j = right[i]
        while j != i:
            down[up[j]] = down[j]; up[down[j]] = up[j]
            size[col_of[j]] -= 1
            j = right[j]
        i = down[i]
# uncover は cover の逆順（up→left方向）で完全に復元する

模範解答

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1
    rows = []
    for _ in range(m):
        k = int(data[idx]); idx += 1
        items = [int(data[idx + t]) for t in range(k)]
        idx += k
        rows.append(items)

    left = [0] * (n + 1)
    right = [0] * (n + 1)
    for c in range(n + 1):
        left[c] = c - 1 if c > 0 else n
        right[c] = c + 1 if c < n else 0

    up = list(range(n + 1))
    down = list(range(n + 1))
    size = [0] * (n + 1)
    col_of = [0] * (n + 1)

    for items in rows:
        first = -1
        prev = -1
        for c in items:
            nid = len(up)
            up.append(up[c]); down.append(c)
            down[up[c]] = nid; up[c] = nid
            size[c] += 1
            col_of.append(c)
            left.append(0); right.append(0)
            if first == -1:
                first = nid; left[nid] = nid; right[nid] = nid
            else:
                left[nid] = prev; right[prev] = nid
                right[nid] = first; left[first] = nid
            prev = nid

    def cover(c):
        right[left[c]] = right[c]; left[right[c]] = left[c]
        i = down[c]
        while i != c:
            j = right[i]
            while j != i:
                down[up[j]] = down[j]; up[down[j]] = up[j]
                size[col_of[j]] -= 1
                j = right[j]
            i = down[i]

    def uncover(c):
        i = up[c]
        while i != c:
            j = left[i]
            while j != i:
                size[col_of[j]] += 1
                down[up[j]] = j; up[down[j]] = j
                j = left[j]
            i = up[i]
        right[left[c]] = c; left[right[c]] = c

    solutions = 0
    def search():
        nonlocal solutions
        if right[0] == 0:
            solutions += 1
            return
        c = right[0]
        best = c
        while c != 0:
            if size[c] < size[best]:
                best = c
            c = right[c]
        c = best
        cover(c)
        i = down[c]
        while i != c:
            j = right[i]
            while j != i:
                cover(col_of[j]); j = right[j]
            search()
            j = left[i]
            while j != i:
                uncover(col_of[j]); j = left[j]
            i = down[i]
        uncover(c)

    search()
    print(solutions)

main()

計算量: 最悪指数時間だが、S heuristic（size最小列優先）により疎な入力に対して実用的な速度になる。1回の `cover`/`uncover` は償却 $O(1)$。

Step-by-Step 解説

Step 1: 疎行列を双方向連結リストで表現

列ヘッダと各行の要素ノードを行方向・列方向で循環双方向リストに繋ぎ、削除操作を $O(1)$ にする。

Step 2: cover(c) で列とその衝突行を一時除外

「アイテム $c$ を行 $r$ で被覆すると決めたので、$c$ を含む他の行はもう選べない」という制約をリンク操作で表現する。

Step 3: uncover(c) は cover(c) の完全な逆操作

削除した順序と厳密に逆の順序でリンクを書き戻せば元の状態に完全復元できる（状態のコピーは不要）。

Step 4: S heuristic による分岐削減

よくあるミス

次のステップ

• 発展問題: 数独を厳密被覆問題として定式化しDLXで解く
• 発展問題: 「高々1回」の被覆を許す一般化被覆（optional columns）に拡張する

自己評価