オフライン・オンライン変換

本記事ではオンライン・オフライン変換と呼ばれる動的計画法(DP)の高速化テクニックの1つを解説していこうと思います。お気持ち理解重視で書くので、冗長かもしれませんがお付き合いください。

高速化テクニックと言いましたが、これ自体は高速化テクニックではなく、「オンラインDP」と呼ばれる種類のDPを、「オフラインDP」と呼ばれる種類のDPに帰着させるテクニックです。一般に前者より後者の方が扱いやすく、結果的に高速化できる場合があるという話になります。

オンラインDPとは

まずオンラインDPとは何か説明していきます。厳密に定義付けられた言葉なのか知りませんが、簡単に言えば「DPテーブルの計算にDPテーブルを用いるDP」ということができます。例えば一般的な2項間漸化式のようなDP

$\begin{align*} \mathrm{DP} _ i=\mathrm{DP} _ {i-1}^3+2 \end{align*}$

のようなものはオンラインDPです。またLCSを求めるDP

$\begin{align*} \mathrm{DP} _ {i,j}=\max(\mathrm{DP} _ {i-1,j},\,\mathrm{DP} _ {i,j-1},\,\mathrm{DP} _ {i-1,j-1}+\mathrm{is\_equal} (s_i,\,t_j)) \end{align*}$

などもオンラインDPです。

オンラインDPの特徴は、一般項などを見つけない限りは、DPテーブルを順番にしたがって埋めていかなければならないということです。この制限は強く、高速化することが難しくなってしまいます。

オフラインDPとは

次にオフラインDPとは何かを説明していきます。簡単に言えば、オンラインDPでないDP、すなわち「DPテーブルの計算にDPテーブルを用いないDP」です。例えば以下のような問題はオフラインDPの一種です。

$\begin{align*} \mathrm{DP} _ j=\max\{|i^2-j|;\,i\in[0,j)\} \end{align*}$

これを見て、これはDPなのか？ただ関数を計算しているだけではないのか？と思うかもしれませんが、極論突き詰めるとオフラインDPとはこういうものです。こんな問題は出ないと思うかもしれませんが、例えば典型的な0-1ナップザック問題を $O(NW)$ で解くDPの遷移は

$\begin{align*} \mathrm{DP} _ {i,j}=\max(\mathrm{DP} _ {i-1,j},\,\mathrm{DP} _ {i-1,j-w_i}+v_i) \end{align*}$

ですが、これは実は(部分的に)オフラインDPになっています。つまり $\mathrm{DP} _ {i}$ なるテーブルを埋めるのに、 $\mathrm{DP} _ {i-1}$ しか使っていないため、すでに $\mathrm{DP} _ {i-1}$ を埋めている状況に於いて、これはオフラインDPと言えます。

オフラインDPの特徴は、テーブルを埋める順序を気にせずに計算して良いということです。これにより、都合よい順番で埋めていくことによって、高速化できることがあります。

お気持ち

ナップザックの2次元DPなどは、DPテーブルに依存していると言えば依存しているので、あくまで部分的にオフラインという話なので、オンラインと言えばオンラインと言えます。つまりこれはオフラインDPを繰り返し適用しているということになります。

これは極論を言えば、任意のオンラインDPも1項だけ埋めるオフラインDPを繰り返してると解釈することもできて、じゃあ何が違うねんみたいな気持ちになるかもしれません。なのでちょっとDPを一般論っぽく話をしてみたいと思います。

DPの添字集合を $I$ (有限集合)、DPのとる値の集合を $V$ として、各 $i\in I$ に対して $\Lambda_i\subset I$ と $F_i:V ^ {\Lambda_i}\to V$ が定まっているとする*1。このとき $I$ 上の半順序が $i\lt j \Leftrightarrow i\in\Lambda_j$ で定まるとする(この順序による有向グラフが閉路を持たなければ良い)。このとき、半順序にしたがった順番で

$\begin{align*} \mathrm{DP} _ {i}=F_i( (\mathrm{DP} _ j;\,j\in\Lambda_i) ) \end{align*}$

を計算することをDPと呼ぶことにする( $i$ が極小元(つまり $\Lambda _ i=\emptyset$ )のときは、 $F_i$ が一点集合からの定値関数となってます)。

このときオンラインDPとは、半順序のトポロジカルソートの自由度が低い(一意乃至ほぼ一意)DP、オフラインDPはその自由度が高いDPと言い換えることができる。

オンライン・オフライン変換

オンライン・オフライン変換というのは、一部のオンラインDPをオフラインDPに変換して計算の自由度を上げようという試みです。オフラインに変換できるならそれは元々自由度が高いじゃないかみたいな気持ちになると思うのですが、まあこれは特殊なDPにしか適用できません(とはいえ、一般的なDPには大体適用できますが)ので、許してください。

条件を整理する前に、前項で定義した語を、簡単のために言い換えておくことにします。以後 $I$ はトポロジカルソートされている*2ものとします。また分かりづらいので、 $I=[0,N)$ として*3、 $\Lambda_i=[0,i)$ とします*4。

条件というのは、 $V$ がモノイドで、任意の $i\in [0,N),\,j\in[0,i)$ について、 $F _ {i,j}:V\to V$ が存在して $F _ i(v _ 0,v _ 1,..,v _ {i-1})=F _ {i,0}(v _ 0) F _ {i,1}(v _ 1) .. F _ {i,i-1}(v _ {i-1})$ (モノイドとしての積)となることです。*5

仰々しく書いていますが、要は参照するDPテーブルを途中で切って、それぞれについて計算した後マージすることができれば良いということです。つまりよく出てくるような $j$ についてなんやかんや計算して、足したり $\max,\min$ を取ったりするものに関してはOKということです*6。

オンラインDPも細かく区切ればオフラインDPという話をしましたが、答えをマージできるがために、うまい具合に区切って、小さなオフラインDPの集まりと考えることができるようになるということです。

では具体的な方法を与えます。 $\mathrm{DP} _ {i,l,m}$ を

$\begin{align*} \mathrm{DP} _ {i,l,m}=\prod _ {j=l} ^ {m-1} F _ {i,j}(\mathrm{DP} _ j) \end{align*}$

と定義します。このとき $\mathrm{solve} (l,\,r)$ を $i\in[l,\,r)$ に対して $\mathrm{DP} _ {i,l,i}$ を計算する関数、 $\mathrm{induce} (l,\,m,\,r)$ を $i\in[m,\,r)$ に対して $\mathrm{DP} _ {i,l,m}$ とします。求めたいのは $\mathrm{DP} _ i=\mathrm{DP} _ {i,0,i}$ に気をつけて、 $\mathrm{solve} (0,\,N)$ となります。

ここで次のような疑似コードで $\mathrm{solve} (0,\,N)$ を呼ぶことを考えます(ただし $e$ は $V$ の単位元)。

dp = [e] * N

induce(l, m, r):
     #hoge

solve(l, r):
    if l + 1 == r:
        return
    m = (l + r) // 2
    solve(l, m)
    A = induce(l, m, r)
    for i in [m, r):
        dp[i] *= A[i]
    solve(m, r)
    return

これが正しく回っていることの確認は各自に任せます*7。

今 $\mathrm{induce} (l,\,m,\,r)$ がオフラインDPとなっています。これは $\mathrm{induce} (l,\,m,\,r)$ が呼ばれる時点で $i\in[l,m)$ に対して $\mathrm{DP} _ i$ がすでに求まっており、 $\mathrm{DP} _ {i,l,m}$ はそれにのみ依存しているためです。よって $\mathrm{induce} (l,\,m,\,r)$ を求める際は、律儀に $m,m+1,..,r-1$ の順番で求めずとも、適当な順番で求めても良いということになります。

以上でいくつかのオフラインDPに分解することができました。ここで計算量を考える。 $N=r-l$ として、 $\mathrm{solve} (l,\,m,\,r)$ の計算量を $T(N)$ , $\mathrm{induce} (l,\,m,\,r)$ の計算量を $M(N)$ とすると

$\begin{align*} T(N)=2T(N/2)+M(N) \end{align*}$

となり、 $T(N)=O(M(N)\log N)$ となります。*8

一つ気を付けたいのは、オンラインDPをなんでもかんでもオフライン化しても、 $M(N)$ が抑えられない限り高速化はされないということです。

具体例

これだけ見てもよくわからないかもしれないので、簡単な問題を解いてみます*9。

整数 $N\leq 10 ^ 6$ と長さ $N$ の整数列 $X$ について、 $\mathrm{DP} _ 0=0$ として、

$\begin{align*} \mathrm{DP} _ {i}=\min\{|\mathrm{DP}[j]-X[i]|; \, j \in [0,i)\} \end{align*}$

により計算される配列を求めよ。

という問題を考えます。愚直にやると $O(N ^ 2)$ かかり間に合いませんが、前からsetに $\mathrm{DP}[i$ ]を突っ込んでいって、set上の二分探索とかで $X[i$ ]に一番近いやつを求めてやれば $O(N\log N)$ で十分高速に求めることができます。

…で終わりだとなんの記事だよって話なんですがこれはオフライン・オンライン変換でも求めることができます。

まずオフラインへの変換は問題によらず変わらないので、 $\mathrm{induce} (l,\,m,\,r)$ を考えます。 $\mathrm{dp}[l,m)$ をソートして、 $i\in [m,r)$ について、ソートした数列上を $X_i$ で二分探索すれば、簡単に求めることができます。これのオーダーは $O(N\log N)$ なので、全体で $O(N\log ^ 2 N)$ で解くことが出来、十分高速です。

C++で実装したものが以下となります。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void chmin(ll&x,ll y){
    if(x>y) x=y;
}

int N;
vector<int> X;
vector<ll> dp;

void induce(size_t l, size_t m, size_t r){
    vector<ll> tmp(m - l);
    copy(dp.begin() + l, dp.begin() + m, tmp.begin());
    sort(tmp.begin(), tmp.end());
    for(size_t i{m}; i != r; ++i){
        size_t j = lower_bound(tmp.begin(), tmp.end(), X[i]) - tmp.begin();
        if(j > 0) chmin(dp[i], abs(tmp[j - 1] - X[i]));
        if(j < m - l) chmin(dp[i], abs(tmp[j] - X[i]));
    }
}

void solve(size_t l, size_t r){
    if(l + 1 == r)
        return;
    size_t m = (l + r) / 2;
    solve(l, m);
    induce(l, m, r);
    solve(m, r);
}

int main(){
    cin >> N;
    X.resize(N);
    for(auto &i : X) cin>>i;
    dp.assign(N,LLONG_MAX);
    dp[0] = 0;
    solve(0,N);
    for(auto &i : dp) cout << i << " ";
    cout << endl;
}

またこのままでも十分高速ですが、 $\mathrm{dp}[l,m)$ をマージソートっぽくソートして、 $X$ も予めマージソートした途中経過を全部覚えておくと、二分探索パートを尺取法っぽくすることで、 $\mathrm{induce} (l,\,m,\,r)$ の計算量を $O(N)$ に抑えられて、全体で $O(N\log N)$ に抑えることができ、setに劣っていないことが分かりますね！*10

まとめ

以上長くなりましたがオフライン・オンライン変換のお話でした。本質パートはかなり単純なんですが、使い所がややこしい影響で、理解しにくいような気がしたので、本質だけ切り抜いて説明しようとしたんですが、なんかごちゃごちゃしすぎて逆に分かりづらいかもしれません。

再掲すると「答えをマージできるがために、うまい具合に区切って、小さなオフラインDPの集まりと考えることができるようになるということです。」←これが本質だと思っています。

なんかわからなかったらTwitterでもコメントでもいいので書いてくれると助かります。以上、ご精読ありがとうございました。

参考文献

動的計画法高速化テクニック（オフライン・オンライン変換） - Qiita

大体これで学んだし、半分以上これのパクリですすいません。

*1:この $F _ i$ は $j\in\Lambda _ i$ を用いて記述されることが多いが、それは $F_i$ が複数乃至全ての $i$ について同時に定義されるがためにそうなっているだけで、単一の $i$ については、そのような $j$ は定数となるから $\mathrm{DP}_j$ のみの関数として与えられることに注意してください

*2:オンラインなら一意なソートと考えていいです

*3:ソート済の有限集合なのでこうして良い

*4: $\Lambda_i\subset {1,\,..\,i-1}$ であり、定義域を広げる分には、広げた分だけ無視すればいいのでOKです

*5:まあ実際はもうちょい弱くてもでき~~ますが、こんなもんでしょう~~て、 $a _ i,b _ i\in V$ を用いて $F _ i(v _ 0,v _ 1,..,v _ {i-1})=a _ iF _ {i,0}(v _ 0) F _ {i,1}(v _ 1) .. F _ {i,i-1}(v _ {i-1})b _ i$ くらいはOKです。まあつまり初期化をいじったり、最後に追加で作用する分にはいいということです。こうしとか無いと初期値が単位元で固定されてよく無いですね(後述の具体例では $i=0$ でだけ初期値をいじってます)。

*6:分かりづらければ、下の具体例の問題を想像していてください

*7:solve(l,r)が呼ばれる時点で、 $i\in[l,r)$ に対して $\mathrm{dp}[i$ =\mathrm{DP} _ {i,0,l}]となっていることなどを、帰納法の中で帰納法回したりすれば示せます。もっと簡単な方法もあるかも

*8:コメントで議論があったので、注釈を入れておきます。まず $M(N)=\Omega(N)$ を仮定しています。これはどちらにせよinduceの後に今までの結果とmergeするパートがあるので、それを合わせれば $\Omega(N)$ にはなるからです。ただ更新する必要がある場所が疎な場合(またその場合に限り) $M(N)=o(N)$ となる場合もありますが、その場合でも $T(N)=\Omega(N)$ にはなりますので注意してください。また例えば $M(N)=O(N ^ 2)$ の場合は、二乗の木DPと同じ計算量で $T(N)=O(N ^ 2)$ となりますが $O(N ^ 2)=O(N ^ 2\log N)$ なので、先の評価でちゃんと上から抑えることはできてます(ところでオーダー表記の等号が非可換なのどうにかならんかね)。