Day 094-Q4 — 彩色数DP（Zeta変換 + 包除原理）

2026-07-17 赤色 Master / Phase 8+ ★★★★★★★★★ 高速ゼータ変換・彩色数・包除原理

問題

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる。彩色数（隣接頂点が異なる色になるよう塗るために必要な最小色数）を求めよ。

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$1 \le N \le 17$
$0 \le M \le N(N-1)/2$
自己ループ・多重辺なし

入出力例

入力例1

3 3
1 2
2 3
1 3

出力例1

3

三角形（完全グラフ$K_3$）は3色必要。

入力例2

4 4
1 2
2 3
3 4
4 1

出力例2

2

4-サイクルは二部グラフなので2色で塗り分け可能。

概念図

$P(G,k)=\sum_{S}(-1)^{|V\setminus S|}i(S)^k$ 1 2 3 三角形: 独立集合は{},{1},{2},{3}のみ $i(S)$=Sの独立な部分集合の個数（SOS変換で計算） $k=1,2$: $P(G,k)=0$（塗れない） $k=3$: $P(G,3)=6\neq0$（$3!=6$通りの3彩色） → 彩色数 = 3

ヒント（段階的開示）

ヒント1: 方向性
$N\le17$なので部分集合$2^N$通りの情報を持つDPが視野に入る。「頂点集合$S$が独立集合かどうか」を全部分集合について求めておくと、彩色に関する強力な式が導ける。
ヒント2: アプローチ
独立集合の指標関数から「$S$の独立な部分集合の個数$i(S)$」を高速ゼータ変換（SOS）で$O(2^NN)$で求める。$k$色での彩色多項式は$P(G,k)=\sum_{S\subseteq V}(-1)^{|V\setminus S|}i(S)^k$（Björklund–Husfeldt–Koivisto）。彩色数は$P(G,k)\neq0$となる最小の$k$。
ヒント3: 誘導（コード骨格） 
# independent[S]: 最下位ビットvで再帰的に判定
low = S & (-S); v = low.bit_length()-1; rest = S ^ low
independent[S] = independent[rest] and (adj[v] & rest) == 0

# count[S] = 独立な部分集合の個数（SOS変換）
for b in range(N):
    for S in range(2**N):
        if S & (1<

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    adj = [0] * n
    for _ in range(m):
        u = int(data[idx]) - 1
        v = int(data[idx + 1]) - 1
        idx += 2
        adj[u] |= (1 << v)
        adj[v] |= (1 << u)

    size = 1 << n
    independent = [False] * size
    independent[0] = True
    for S in range(1, size):
        low = S & (-S)
        v = low.bit_length() - 1
        rest = S ^ low
        independent[S] = independent[rest] and (adj[v] & rest) == 0

    count = [1 if independent[S] else 0 for S in range(size)]
    for b in range(n):
        bit = 1 << b
        for S in range(size):
            if S & bit:
                count[S] += count[S ^ bit]

    popcount = [bin(S).count('1') for S in range(size)]

    poly = [1] * size
    for k in range(1, n + 1):
        for S in range(size):
            poly[S] *= count[S]
        total = 0
        for S in range(size):
            term = poly[S]
            if (n - popcount[S]) % 2 == 1:
                term = -term
            total += term
        if total != 0:
            print(k)
            return

    print(n)


main()
計算量: 独立集合判定 $O(2^N)$、ゼータ変換 $O(2^N N)$、各kでの評価 $O(2^N)$ を最大N回で全体 $O(2^N N)$。

Step-by-Step 解説

1隣接ビットマスク構築
頂点vに隣接する頂点集合をビットマスクadj[v]として持つ。
2独立集合の判定
最下位ビットvを取り出し「$S\setminus\{v\}$が独立」かつ「vが$S\setminus\{v\}$と非隣接」を再帰的にチェック。
3高速ゼータ変換
各ビットについて「そのビットを含む集合に含まない集合の値を足す」操作をN回繰り返し、部分集合和を得る。
4包除原理で評価
$i(S)^k$は「k色でSの部分集合に収まる塗り方の数」に対応し、包除原理でちょうどV全体を覆う彩色数を数える。
5最小のkを探索
$k=1$から順に$P(G,k)\neq0$になるまで試す。$k=N$では必ず正になるため必ず終了する。

よくあるミス

ミス原因正しい書き方
独立集合判定を毎回$O(N^2)$の全ペアチェックで実装ビットマスク再帰式を使っていない最下位ビットを使った$O(2^N)$のDP
ゼータ変換のループ順序を間違えるSOS変換パターンの理解不足外側=各ビット、内側=全集合、if S & bitの中で加算
符号計算でbin().count()を毎回呼び低速化前計算していないpopcount配列を事前に$O(2^N)$で構築
$k=0$から探索開始彩色数の下限の勘違い$k=1$からループ開始

次のステップ

  • 発展: k色での彩色方法の総数自体を求める（本問のtotalがまさにその値）
  • 発展: Nが大きい場合の近似彩色アルゴリズムとの比較
  • 次回予告: Welzl's Algorithm（最小包含円）

自己評価

自分の回答

気づき・メモ