ei1333's page

ホーム > Wiki

いろいろな動的計画法

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

ぐっと睨むタイプのやつ

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

ダブリング

全要素について, 次の要素が容易に計算できるとき $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]$ を満たすものである。

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$ 種類を効率的に行うテクである。

包除原理

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

$\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 などによって個数によってまとめられることがあり, その場合は計算量を落とすことが可能で有用である。

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

Bit-DP

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

問題例

参考資料