差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:dynamic_programming:subset_convolution [2020/02/12] – ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/14] (現在) – [高速ゼータ変換 高速メビウス変換] ikatakos | ||
---|---|---|---|
行 6: | 行 6: | ||
* [[https:// | * [[https:// | ||
- | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 | + | 競プロでたまに出てくるアルゴリズムで、ちょっと直感的な理解が難しい故か、解説記事がいろいろ書かれている。 |
- | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるのか不明だが、まぁそこは気にせず自分用メモとして書いておく。 | + | 更にそれを整理したキュレーション記事も既にあるため、今更独自に書く意味があるか微妙だが、まぁそこは気にせず自分用メモとして書いておく。 |
===== 定義 ===== | ===== 定義 ===== | ||
- | 集合についての数え上げを行う動的計画法の一種。 | + | 集合についての畳み込みを行う動的計画法の一種。 |
* ある $N$ 個のものがある | * ある $N$ 個のものがある | ||
行 19: | 行 19: | ||
部分集合 | 部分集合 | ||
- | * それぞれの部分集合につき、何らかのスコアが決まっている | + | * それぞれの部分集合 |
- | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求める | + | * ある部分集合 $S_i$ について、$S_i \subseteq T$ となるような全ての $f(T)$ の総和を求めたい |
部分集合 | 部分集合 | ||
- | | + | |
| | ||
- | S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | + | Si = {1} |
- | 4 + | + | → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} |
+ | | ||
* これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | ||
部分集合 | 部分集合 | ||
- | | + | |
Z変換 | Z変換 | ||
- | * また、Z変換後から元のスコアを逆算する処理を「メビウス変換」という。 | + | * また、Z変換後から元の |
- | | + | |
| | ||
Z変換 | Z変換 | ||
+ | ただし、競プロ界隈ではよく使われるこの定義は限定的なものであり、本来のゼータ変換はもう少し広い範囲を指す。 | ||
+ | |||
+ | * [[wpjp> | ||
+ | * [[https:// | ||
==== 定義揺れ ==== | ==== 定義揺れ ==== | ||
行 56: | 行 61: | ||
Z変換① | Z変換① | ||
- | ===== 方法 ===== | + | ===== 実装方法 ===== |
集合をbitで表す。 | 集合をbitで表す。 | ||
行 135: | 行 140: | ||
===== 意味合い ===== | ===== 意味合い ===== | ||
- | ビット演算がよくわからなさを増しているが、意味合いは比較的単純であり、 | + | ビット演算が、何やってるかよくわからない感を増しているが、意味合いは比較的単純であり、 |
集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。 | 集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。 | ||
行 162: | 行 167: | ||
===== バリエーション ===== | ===== バリエーション ===== | ||
+ | |||
+ | ==== 加算以外の演算 ==== | ||
ゼータ変換に適用する演算は必ずしも加算である必要は無い。 | ゼータ変換に適用する演算は必ずしも加算である必要は無い。 | ||
行 176: | 行 183: | ||
それを考えると、メビウス変換は逆演算が可能でなければならない? maxは逆演算できないので、メビウス変換は適用できないと思われる。 | それを考えると、メビウス変換は逆演算が可能でなければならない? maxは逆演算できないので、メビウス変換は適用できないと思われる。 | ||
- | | + | ==== 包含以外の畳み込み ==== |
+ | |||
+ | ゼータ変換後の $f$ を $\zeta(f)$ とする。ゼータ変換①を式で表すと | ||
+ | |||
+ | | ||
+ | |||
+ | ここで $S$ はbitフラグを示す一般の数字と解釈すると、BitAND演算で示すことも出来る。 | ||
+ | |||
+ | * $\zeta(f)(i) = \sum_{i \ AND \ j=i} f(j)$ | ||
+ | |||
+ | このBitAND演算を変えて畳み込みを行うバリエーションも存在する。特にゼータ変換②は、BitORにしたものである。 | ||
+ | |||
+ | * ゼータ変換② | ||
+ | * $\zeta(f)(i) = \sum_{i \ OR \ j=i} f(j)$ | ||
+ | * maxによる畳み込み | ||
+ | * $\zeta(f)(i) = \sum_{\max(i, | ||
+ | * 単なる累積和っぽい? | ||
+ | * 最大公約数、最小公倍数による畳み込み | ||
+ | * $\zeta(f)(i) = \sum_{\gcd(i, | ||
+ | * $i$ の倍数であるような $j$ | ||
+ | * $\zeta(f)(i) = \sum_{{\rm lcm}(i, | ||
+ | * $i$ の約数であるような $j$ | ||
* [[http:// | * [[http:// | ||