差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:dynamic_programming:subset_convolution [2020/02/12] – [バリエーション] ikatakos | programming_algorithm:dynamic_programming:subset_convolution [2020/02/13] – [定義] ikatakos | ||
---|---|---|---|
行 11: | 行 11: | ||
===== 定義 ===== | ===== 定義 ===== | ||
- | 集合についての数え上げを行う動的計画法の一種。 | + | 集合についての畳み込みを行う動的計画法の一種。 |
* ある $N$ 個のものがある | * ある $N$ 個のものがある | ||
行 20: | 行 20: | ||
* それぞれの部分集合につき、何らかのスコアが決まっている | * それぞれの部分集合につき、何らかのスコアが決まっている | ||
- | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求める | + | * ある部分集合 $S$ について、$S \subseteq T$ となるような全ての $T$ のスコアの総和を求めたい |
部分集合 | 部分集合 | ||
行 26: | 行 26: | ||
| | ||
S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | S = {1} → T = {1}, {0, 1}, {1, 2}, {0, 1, 2} | ||
- | | + | スコアの総和 |
* これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | * これを全ての部分集合について行うのが「ゼータ変換」であり、高速に行うアルゴリズムを「高速ゼータ変換」という。 | ||
行 40: | 行 40: | ||
Z変換 | Z変換 | ||
+ | ただし、競プロ界隈ではよく使われるこの定義は限定的なものであり、本来のゼータ変換はもう少し広い範囲を指す。 | ||
+ | |||
+ | * [[wpjp> | ||
+ | * [[https:// | ||
==== 定義揺れ ==== | ==== 定義揺れ ==== | ||
行 135: | 行 139: | ||
===== 意味合い ===== | ===== 意味合い ===== | ||
- | ビット演算がよくわからなさを増しているが、意味合いは比較的単純であり、 | + | ビット演算が、何やってるかよくわからない感を増しているが、意味合いは比較的単純であり、 |
集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。 | 集合の要素数を $N$ として「$N$ 次元の $(2 \times 2 \times ... \times 2)$ 配列の各次元について後ろの要素を前の要素に足す」という処理を行っている。 | ||