競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。
更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるか微妙だが、まぁそこは気にせず自分用メモとして書いておく。
集合についての畳み込みを行う動的計画法の一種。
A = {0, 1, 2}
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
f(S) 3 1 4 1 5 9 2 6
Si = {1}
→ T = {1}, {0, 1}, {1, 2}, {0, 1, 2}
f(T)の総和 4 + 5 + 2 + 6 = 17
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
f(S) 3 1 4 1 5 9 2 6
Z変換 31 21 17 18 11 15 8 6
f(S) 3 1 4 1 5 9 2 6
ゼータ変換↓ ↑メビウス変換
Z変換 31 21 17 18 11 15 8 6
ただし、競プロ界隈ではよく使われるこの定義は限定的なものであり、本来のゼータ変換はもう少し広い範囲を指す。
$S \subseteq T$ でなく $S \supseteq T$ であるような $T$ について求めることを指す場合もある。
ここでは、$S \subseteq T$ の方をゼータ変換①、$S \supseteq T$ の方をゼータ変換②と称する。
②は、部分集合の補集合を取ってから①のゼータ変換を行った結果と一緒になる。
部分集合 {}, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}
スコア 3 1 4 1 5 9 2 6
Z変換② 3 4 7 4 13 14 10 31
補集合 {0, 1, 2}, {1, 2}, {0, 2}, {0, 1}, {2}, {1}, {0}, {}
スコア 3 1 4 1 5 9 2 6
Z変換① 3 4 7 4 13 14 10 31
集合をbitで表す。
i 2 1 0
---------
0 0 0 0 ...{}
1 0 0 1 ...{0}
2 0 1 0 ...{1}
3 0 1 1 ...{0, 1}
4 1 0 0 ...{2}
5 1 0 1 ...{0, 2}
6 1 1 0 ...{1, 2}
7 1 1 1 ...{0, 1, 2}
元のスコアをこの順に対応させた配列を作り、以下の要領で更新する。
n = 3 # 集合の要素数
dp = [3, 1, 4, 5, 1, 9, 2, 6] # 2^n の長さ
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit == 0:
dp[i] += dp[i | bit]
print(dp)
# => [31, 21, 17, 11, 18, 15, 8, 6]
n = 3 # 集合の要素数
dp = [3, 1, 4, 5, 1, 9, 2, 6] # 2^n の長さ
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit:
dp[i] += dp[i ^ bit]
print(dp)
# => [3, 4, 7, 13, 4, 14, 10, 31]
n = 3 # 集合の要素数
dp = [31, 21, 17, 11, 18, 15, 8, 6] # ゼータ変換①後
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit == 0:
dp[i] -= dp[i | bit] # + を - にしただけ
print(dp)
# => [3, 1, 4, 5, 1, 9, 2, 6]
n = 3 # 集合の要素数
dp = [3, 4, 7, 13, 4, 14, 10, 31] # ゼータ変換②後
for j in range(n):
bit = 1 << j
for i in range(1 << n):
if i & bit:
dp[i] -= dp[i ^ bit] # + を - にしただけ
print(dp)
# => [3, 1, 4, 5, 1, 9, 2, 6]
ビット演算が、何やってるかよくわからない感を増しているが、意味合いは比較的単純であり、 集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。
i 0 1 A [ a0 a1 ] 元の配列 Z [ a0+a1 a1 ] ゼータ変換後
$0 \subseteq 1$ なので、$Z[0]$ は $A[0]+A[1]$ となる。（たった2要素だが）後ろから累積和を取った感じ。
bit列は1次元だが、2次元にして考えてみる。
A [ [ a00 a01 ]
[ a10 a11 ] ]
Z' [ [ a00+a01 a01 ] 横方向に後ろからの累積和（途中経過）
[ a10+a11 a11 ] ]
Z [ [ a00+a01+a10+a11 a01+a11 ] 縦方向に下からの累積和
[ a10+a11 a11 ] ]
次元が増えても、このように1次元ずつ後ろの要素を前の要素に足していくことを繰り返したものとなる。
ゼータ変換に適用する演算は必ずしも加算である必要は無い。 圏論でいう モノイド であれば、同様のアルゴリズムでまとめ上げることが可能である。
A [ [ a00 a01 ]
[ a10 a11 ] ]
↓演算を max としたゼータ変換
Z [ [ max(a00,a01,a10,a11) max(a01,a11) ]
[ max( a10, a11 ) max( a11 ) ] ]
それを考えると、メビウス変換は逆演算が可能でなければならない？ maxは逆演算できないので、メビウス変換は適用できないと思われる。
ゼータ変換後の $f$ を $\zeta(f)$ とする。ゼータ変換①を式で表すと
ここで $S$ はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。
このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。