こんにちは。株式会社オプティマインドの伊豆原と申します。
今回は自社の競プロ部の活動の一環として、アルゴリズム紹介記事として高速ゼータ変換について話させて頂きます。なお、当社の競プロ部に関しては以下のような紹介記事がございます。
高速ゼータ変換について
有限集合$S$とその部分集合を引数にとる関数$f : \mathcal{P}(S) \to \mathbb{R}$が与えられた時、そのゼータ変換$g : \mathcal{P}(S) \to \mathbb{R}$が以下のように定義されます。
$$g(T) := \sum_{U \subset T} f(U)$$
競技プログラミングでは小さい集合(要素数64個以下など)の管理をビットで行うことが多く、要素数$N$の集合$S$の部分集合は$0$から$2^N-1$までの整数(のビット表現)で表されます。その表現を使って関数$f : [0,2^N-1] \to \mathbb{R}$のゼータ変換$g$を求めるPythonコードを書きますと、"愚直"に計算して$\mathcal{O}(4^N)$、"部分集合の部分集合"でうまくループを廻して$\mathcal{O}(3^N)$となります。
# 配列F : F[i] = f(i), i \in [0,2^N-1]
# O(4^N)
G = [0]*(2**N) # G[i]=g(i)
for i in range(2**N):
for j in range(2**N):
if i&j == j: # (jのビット) ⊆ (iのビット)
G[i] += F[j]
# O(3^N)
G = [0]*(2**N)
for i in range(2**N):
j = i
while True: # (iのビット)の部分集合のみでループ
G[i] += F[j]
if j == 0:
break
j = (j-1) & i # & i で部分集合以外を飛ばす
この計算を高速ゼータ変換と呼ばれる方法で行いますと、計算量を$\mathcal{O}(N2^N)$に抑えることができます。
G = F.copy() # copy
for j in range(N):
b = 1<<j
for i in range(2**N):
if i&b:
G[i] += G[i^b] # i^bはiの(右から)jビット目が少ない状態
言葉で説明しますと、任意の要素$x \in S$ごとにその要素を含んでる任意の部分集合$x \in T$に対して$g(T) += g(T\setminus \lbrace x \rbrace)$と足し上げる計算になります。たとえば$|S|=3$として、集合のビット表現において左から1ビット目に着目しますと、行われる足し算は$g(100)+=g(000),g(110)+=g(010),g(101)+=g(001),g(111)+=g(011)$となります。
図を用いた説明
この計算をもう少し視覚的にしてみます。
一般に有限集合の部分集合全体は束構造を成します。たとえば要素数3の集合の部分集合はハッセ図 の形で直方体の各頂点に割り当てて表現することができます。この表現を基に考えると、先の高速ゼータ変換は下記の図の水色の矢印において、始点から終点の方向に順に足し上げていることが分かります。
あたかも縦・奥・横の各"次元"ごとに足し上げているようですが、これは有限集合$S$の部分集合全体の成す束$L=\mathcal{P}(S)$がBoolean束$\mathbb{B}=\{0,1\}$の直積として書けることに由来します(つまり$\mathcal{P}(S) \cong \mathbb{B}^{|S|}$)。つまり高速ゼータ変換とは、"ゼータ変換を行う束が直積に分解できるときに各次元でゼータ変換する"という下の逐次積分のような計算と考えることができます。
$$g = \int_\mathbb{B}\cdots\int_\mathbb{B}f(x_1 x_2 \cdots x_n)dx_1 \cdots dx_n$$
特に分解先の束が$\mathbb{B}=\{0,1\}$や有限区間$[0,N]$みたいな時は、inplaceな累積和がゼータ変換になるのでとりわけ高速に計算することができる、という感じです。
計算量について
この考えに基づいて計算量を考えてみます。
有限集合$S$の部分集合の成す束$\mathcal{P}(S)$について$\mathcal{P}(S) \cong \mathbb{B}^{|S|}$でした。$\mathbb{B}=\{0,1\}$でのゼータ変換はinplaceな累積和(というか足し算1回)で済み、それを各次元ごとに$2^{|S|-1}$回行う必要があります。次元は$|S|$次元なので、計算量は定数倍を除いて$\mathcal{O}(|S|2^{|S|})$となります。
他の例ですと、(inplaceな)二次元累積和なども高速ゼータ変換と見做せます。束として下記のような格子を考えますと、これは$[0,H]\times [0,W]$という部分束の直積になります。そのため各次元でのゼータ変換はinplaceな累積和で計算できるので、全部で$H(W+1)+(H+1)W$回の計算でゼータ変換を求めることができます。よって計算量は$\mathcal{O}(HW)$です。
結び
以上、高速ゼータ変換を紹介させて頂きました。分解する部分束がもうちょっと複雑な構造を持つ高速ゼータ変換で面白そうな例を見つけてみたいですね。
読んで頂きありがとうございました。