ei1333's page

いろいろな動的計画法

まとめておかないと忘れてしまうため(ア

ぐっと睨むタイプのやつ

漸化式をぐっと睨むと, 累積和やセグメント木で加速できることがある。

ダブリング

全要素について, 次の要素が容易に計算できるとき $x_i$ 個先の要素を求めるクエリに対して, 前計算 $(N \log N)$, クエリ $(\log N)$ で求めることができる。

前計算では $\mathrm{table}[k][i]$ に対して $i$ 番目の要素の $2^k$ 個次の要素を格納する(存在しないとき $-1$)。

位置 $p_i$ から $x_i$ 個先の要素を求めるクエリに答える際には, $x_i$ を二進展開して考える。上位 bit から見ていって, $k$ 桁目の bit が $1$ のとき $2^k$ 次の要素に進むことを繰り返す。この $1$ 回ぶんの操作は$p_i = \mathrm{table}[k][p_i]$ をすることで行える。

単純に $x_i$ 個先の要素を求めるだけではなくて, 現在位置から $x_i$ 個先までの要素の総和や, $x_i$ 個先までの要素のうちの min などを求めたいときがある。ここでは総和を求める例を考える。この場合は前計算によって $\mathrm{table}[k][i]$ を埋めた後に, $\mathrm{sum}[k][i] := $ $[i, i + 2^k)$ の総和を埋める計算を行う。$\mathrm{sum}[0][i]$ に $i$ 番目の要素の値を格納してあるとすると, $\mathrm{sum}[k+1][i]$ は $\mathrm{sum}[k][i]$ (つまり $[i, i+2^k)$) に $\mathrm{sum}[k][\mathrm{table}[k][i]]$ (つまり $[i+2^k, i+2^k+2^k=i+2^{k+1})$) を加えたものなので, これをいい感じの順序で計算すればよい。クエリに答える時は, $p_i = table[k][p_i]$ をするとき合計に $\mathrm{sum}[k][p_i]$ を加えることで求められる。

またダブリング配列を使った二分探索も同じ計算量で行える。位置 $p_i$ からで合計が $s_i$ 以下であるような最大の $x_i$ を求めたいとする。上位 bit から見ていって, $\mathrm{sum}[k][p_i]$ が $s_i$ 未満であるとき $s_i$ から $\mathrm{sum}[k][p_i]$ をひいて $p_i = \mathrm{table}[k][p_i]$ として次に移動することを繰り返せばよい。次に移動したときの bit を保存していくと最終的なそれが最大の $x_i$ である。

ダブリングを用いたLCAも同じような二分探索をしている。まず頂点 $u, v$ のLCAを求める。ここで $d_i$ を頂点 $i$ の深さとし, $d_u \le d_v$ を仮定する($d_u \gt d_v$ のときは swap すればよい)。まず $d_v$ を $d_v - d_u$ 個だけ親に遡らせて深さを合わせる。ここで $d_v$ が $d_u$ と一致したらそれが LCA。それ以外のときは, 上位bit から $u, v$ 双方の $2^k$ 先の親が異なれば共に遡ることを繰り返して, 双方の親ではない直前の頂点を求める。するとその親がLCAとなる。

Monge

コスト $C[i][j]$ が Monge かつ単調ならば色々な高速化ができる。Monge とは, $\forall a \le b \le c \le d$ に対し $C[a][c] + C[b][d] \le C[a][d] + C[b][c]$, 単調とは $C[b][c] \le C[a][d]$ を満たすものである。

Divide-and-Conquer-Optimization

$\displaystyle dp[i][j] = \min_{0 \le k \lt j} \{dp[i - 1][k] + C[k][j]\}$

例題として次のような問題を考える。長さ $n$ の配列 $w_i$ が与えられる。部分列の$w_i$ の二乗和の総和が最小になるように, $m$ 個の連続した部分列に分割する。$dp[i][j]$ を区間 $[0, j)$ を $i$ 個の配列で被覆するときの二乗和の最小値とし, $C[i][j]$ を区間 $[i, j)$ の二乗和と定義すれば, 上記のような漸化式の形となる。

単純なDPを行うと計算量が $O(m n^2)$ かかる。しかしながらここで $A[i][j] := dp[i][j]$ を最小とする $k$ とおくと, $\forall p$ に対し $A[i][p] \le A[i][p + 1]$ をみたす。これを利用すると計算量を $O(mn \log n)$ に落とすことができる。$m$ 通りの $i$ に対して $O(n \log n)$ を行うイメージ。ある $i$ に対し, 任意の $j$ に対して解を求めたいとする。最初に $O(n)$ かけて $dp[i][\frac n 2]$ を求めると, そのときの $A[i][\frac n 2]$ を用いて $[0, \frac n 2), [\frac n 2 + 1, n)$ のそれぞれの区間において, 探索すべき範囲が定まる。これを再帰的に行う。探索範囲は全体で $2n$ を超えないため $O(n \log n)$ である。

Knuth-Optimization

$\displaystyle dp[i][j] = \min_{i \lt k \lt j} \{dp[i][k] + dp[k][j]\} + C[i][j]$

単純なDPを行うと計算量が $O(n^3)$ かかる。しかしながらここで $A[i][j] := dp[i][j]$ を最小とする $k$ とおくと, $dp[i][j]$ に対し $k$ となる可能性のある区間は $A[i][j - 1] \le k \le A[i + 1][j]$ に限定される。これを用いると $O(n^2)$ となる。

Convex-Hull-Trick

直線の集合 $L = \{f_1(x), f_2(x), \dots, f_k(x)\}$ (ここで $f_i(x) = a_i x + b_i$) に対して, 集合 $L$ への新たな直線の追加クエリと, $x$ が与えられたときに集合 $L$ のうち最小値をとるような直線の値を求める最小値クエリの $2$ 種類を効率的に行うテクである。

追加クエリについて, 与えられる $a_i$ が単調

直線を先頭か末尾に加えるかのどちらかになるため, Deque を使えばこれを $O(1)$ で行える。また最小値クエリに関しては二分探索すれば全体で $O(n \log n)$ だが, 与えられる $x$ が単調増加であれば尺取りできるため全体でも $O(n)$ となる。

追加クエリについて, 与えられる $a_i$ が単調ではない場合

直線の位置を二分探索で求めて気合いをすることになる。悲しいね。実装に $O(n!)$ 時間かかってつらいが, 計算量は全体でも $O(n \log n)$ となる。

包除原理

全体から, 重複している集合を取り除く原理。最も基本的な包除原理の形への変換として次式を与える。

$\displaystyle |\bigcap_{i=1}^{n} A_i| = |\overline{\bigcup_{i=1}^{n} \overline{A_i}}|$

$A_i$ が何らかの条件を表している。つまり全ての条件 $A_i$ を満たす集合を数え上げたい時に, $\overline{A_i}$ の和集合を数え上げる形に変形することにより包除原理を使える形に落とせることを示している。条件 $A_i$ の部分集合を指定したときに条件を全て違反するようなものの個数(指定した条件以外の条件については満たしていても満たしていなくてもよい) を求めてそれらを部分集合の条件の個数の偶奇に応じて足し引きすればよい。条件は DP などによって個数によってまとめられることがあり, その場合は計算量を落とすことが可能で有用である。

以下個数でまとめられるパターンについて例を挙げる。結構機械的にできる。

完全順列

長さ $N$ の順列 $\{a_i\}$ で, すべての $i$ について $a_i \ne i$ を満たすものの個数

もとの条件: $a_1 \ne 1$ and $a_2 \ne 2$ and ... $a_N \ne N$
条件の否定: $a_1 = 1$ or $a_2 = 2$ or ... $a_N = N$
愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数は $(N-|B|)!$ である。$B$ で選ばれた要素以外は自由に決めて良いので, 残りの要素数の階乗通りある。
効率的解法: $(N-|B|)!$ は条件の個数のみに依存している。条件が $k$ 個の部分集合の個数は ${}_N \mathrm{C}_k$ である。よって条件を否定する順列の個数は $\displaystyle \sum_{k=1}^{N} (-1)^{k+1} (N-k)! {}_N \mathrm{C}_k$ であり, これを全体の $N!$ から引いたものが答えである。$O(N)$。

$|a_i - i| \ne K$ の順列(AGC005 D ~K Perm Counting)

長さ $N$ の順列 $\{a_i\}$ で, すべての $i$ について $|a_i - i| \ne K$ を満たすものの個数

もとの条件: $a_1 - 1 \ne K$ and $a_2 - 2 \ne K$ and ... $a_N - N \ne K$ and $a_1 + 1 \ne K$ and $a_2 + 2 \ne K$ and ... $a_N + N \ne K$
条件の否定: $a_1 - 1 = K$ or $a_2 - 2 = K$ or ... $a_N - N = K$ or $a_1 + 1 = K$ or $a_2 + 2 = K$ or ... $a_N + N = K$
愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数は $0$ または $(N-|B|)!$ である。$B$ のそれぞれの要素から, 実際に割り当てる値 $a_i = K + i$ または $a_i = K - i$ に辺をはる。ここで次数が $2$ 以上の頂点が生まれたら, そのような割り当て方は存在しないので $0$ である。それ以外は指定した要素以外を自由に決められるため $(N-|B|)!$ である。
効率的解法: 次数が $1$ 以下というのは, つまり二部グラフのマッチングの一例である。$a_i = K + i$ または $a_i = K - i$ に辺をはったグラフを考えると, これは $\bmod K$ で $K$ 個の直線グラフに分けられる。長さ $M$ の直線グラフについて $K$ 個マッチさせる個数は ${}_{M-k} \mathrm{C}_{k}$ らしいので, これを $K$ 個の直線の各個数について求めて DP で数え上げる。DPテーブルは dp[$k$] := $K$ 個の直線グラフから $k$ 個マッチングさせる組み合わせとすればよい。

自分以外の連結成分に移動する順列 (ARC087 F - Squirrel Migration)

長さ $N$ の順列 $\{a_i\}$ で, それぞれの要素には色 $c_i$ が塗られている。すべての $i$ について $c_i \ne c_{a_i}$ を満たすものの個数

もとの条件: $c_1 \ne c_{a_1}$ and $c_2 \ne c_{a_2}$ and ... $c_N \ne c_{a_N}$
条件の否定: $c_1 = c_{a_1}$ or $c_2 = c_{a_2}$ or ... $c_N = c_{a_N}$
愚直な解法: 条件の部分集合 $B$ をとってきたとき, それらを満たす順列の個数を考える。まず $B$ で指定された以外の要素は自由に決めて良いため $(N-|B|)!$ が全体に掛かる。 $B$ で指定された要素のみを考える。$T_k$ を色 $k$ の個数, $S_k$ を $B$ 内での色 $k$ の要素の個数と定義する。それぞれの色について, 自分の色に移動するような順列の個数は ${}_{T_k} \mathrm{ P }_{S_k}$ である。よって $\displaystyle (N-|B|)! \prod_{k} {}_{T_k} \mathrm{ P }_{S_k}$ となる。
効率的解法: 色を順番に追加していく DP を考える。 DP テーブルを dp[$k$] := ($k$ 個の要素を部分集合 $B$ に含めたときの順列の個数) $÷ (N-|B|)!$ とする。 $x$ 個の同じ色を追加するときその選び方は ${}_{T_k} \mathrm{ C }_{x}$ である。これに ${}_{T_k} \mathrm{ P }_{x}$ を掛けたものが組み合わせの数である。あとは普通に遷移させればよくて $O(N^2)$ ($O(N^3)$ っぽいが $O(N^2)$ であることがわかる)。

Bit-DP

いろいろなアなテクがある。

高速ゼータ変換, 高速メビウス変換

集合 $S$ に対してある値を返す関数 $f(S), g(T)$ を定義する。ゼータ変換とメビウス変換の定義は以下の通りである。

ゼータ変換: $f(S) = \sum_{S \subseteq T} g(T)$
メビウス変換: $g(T) = \sum_{S \subseteq T} (-1)^{|T-S|} f(S)$

ゼータ変換はすべての $g(T)$ の値がわかっているとき, すべての集合 $S$ について $f(S)$ を求める操作である。例えば $f(1010) = g(1111) + g(1110) + g(1011) + g(1010)$ である。やっていることは, 集合 $S$ を部分集合に含む全集合の総和を求めることである。

メビウス変換はすべての $f(S)$ の値が分かっているとき, すべての集合 $T$ について $g(T)$ を求める操作である。例えば $g(1010) = f(1010) - f(1000) - f(0010) + f(0000)$ である。えーとこの式をみてもわかりにくいアなんですが, 要するにゼータ変換の逆変換をしていることを思うと良い。

高速ゼータ変換や高速メビウス変換は, 上の処理を $O(n 2^n)$ で行う処理である。

Codeforces #257 Div1 D. Jzzhu and Numbers は高速ゼータ変換を適用可能である。長さ $K$ の数列 $A_i$ が与えられたとき, 部分列中の全要素のandが $0$ となるものの数を求める問題である。$g(T)$ を数列中の $T$ の個数と定義すると, $f(S)$ は数列中で $S$ を部分集合に含むものの個数となる。

AOJ 2446: Enumeration は高速メビウス変換を使う問題である。$f(S)$ を $m$ 以下の整数での $S$ の lcm の倍数の個数と定義する。すると $g(T)$ は $m$ 以下の整数についてその要素の少なくと割り切れるものの個数になる。

えー理解していないため(悲しいね)

部分集合の列挙を用いたDP

それぞれの頂点集合 $S_i$ に対し, その部分集合 $T_i$ を試すDPは $O(3^n)$ で行える。これは $n$ 個の頂点を $T_i$, $S_i - T_i$, その他に分ける方法を試していることと等価であることからいえる。

具体的に頂点集合 $bit$ の部分集合を列挙するためには, 以下のコードを用いれば良い。変数 $i$ に入るものが $bit$ の部分集合である。 $i = \emptyset$ を許容しないことに注意すること(許容するときは別途処理する)。

補足として, $O(3^n)$ のDPは基本的に $O(2^n n^2)$ くらいで何かを前計算しておいて, それを用いて計算量を削減することが多い。

ここで非自明っぽい例題として次のような問題を考える。$n(2 \le n \le 16)$ 頂点の単純な無向グラフが与えられる。部分グラフのうち連結であるようなものの個数を求めよ。再帰関数 $rec(bit)$ を頂点集合 $bit$ を見たとき, それが連結グラフである組み合わせと定義する。最終的な答えは $rec(2^n - 1)$ である。また $E(bit)$ を $bit$ 内同士を結ぶ辺の本数と定義する。まず基底条件として $rec(0) = 1$ である。考察すると $\displaystyle rec(bit) = 2^{E(bit)} - \sum_{bit_0 \in i, i \subset bit} rec(i) 2^{E(bit - i)}$ ということがわかる。頂点集合 $bit$ からなるグラフを考える。すべての辺の選び方は $2^{E(bit)}$ 通りであり, これから非連結な選び方を除いたものが連結なグラフの個数である。非連結なグラフはある $1$ 頂点 $bit_0$ を固定して, その頂点と同じ連結成分に属する頂点集合 $i$ はどれかで分別できる。よって $rec(i) 2^{E(bit - i)}$ を $bit_0 \in i$ を満たすすべての部分集合について計算してひけばよい。

問題例

検証済(Divide-and-Conquer-Optimization)CF #438 F. Yet Another Minimization Problem(Submittion: #31050682)
検証済(Knuth-Optimization)AOJ2415 刺身
検証済(Convex-Hull-Trick)AOJ2725 Live Programming