2017-12-12

競技プログラミングAdventCalender2017の12日目の記事です。この記事では、最近コンテストでしばしば見かける「インラインDP」というテクニックに付いて説明します。まぁ「インラインDP」と呼んでいるのはおそらく自分だけで、他の人たちは「segtreeを使ったDP高速化のやつ」とか「実家」（典型テクニックだから、という意味で）とか呼んでいますが、おそらくこの呼び方が自分では一番中身をあらわしていると思うので、それで行こうと思います。

さて、インラインDPの例題として次の問題の解法を考えていきましょう。

ARC073F問題 Many Moves

まずこの問題を解くためには、

dp[何個目までのクエリを処理したか][1つ目のコマの場所][2つ目のコマの場所]:=それを達成する最小の秒数

という状態を持ってDPすれば解けます。しかし、i個目のクエリを処理した直後は、必ず片方のコマは $x_i$ に置かれているので、

dp[何個目までのクエリを処理したか][もう片方のコマの場所]:=それを達成する最小の秒数

という状態を持てばいいです。これは以下のような2次元DPで、i個目までのクエリを処理した、というもののiを0からNまで加算しつつ埋めていけば解けます。しかしこれでは状態量が最大NQとなり、実行時間的にもメモリ的にも到底収まりません。

そこで、計算量を改善するために、まずは遷移を考えてみましょう。dp[i][j]、つまりi番目までのクエリを処理して2つのコマがそれぞれ位置 $x_i$ と位置 $j$ にある場合、次のi+1番目のクエリを処理するために、

・位置 $x_i$ にあるコマを位置 $x_{i+1}$ に動かす

・位置 $j$ にあるコマを位置 $x_{i+1}$ に動かす

という2通りの方法があり、それぞれに対応するDPの更新式は

$dp[i+1\][j\]=min(dp[i+1\][j\]\:,\:dp[i\][j\]+|x_i-x_{i+1}|)$

$dp[i+1\][x_i\]=min(dp[i+1\][x_i\]\:,\:dp[i\][j\]+|j-x_{i+1}|)$

となります。

ここで、更新式の遷移元ではなく遷移先に注目すると（界隈でよく言われている呼び方で言うと、配るDPから貰うDPに変換すると）

$dp[i+1\][j\]=dp[i\][j\]+|x_i-x_{i+1}| (j!=x_{i})$

$dp[i+1\][j\]=\min_{k=1,...,N}dp[i\][k\]+|k-x_{i+1}| (j=x_{i})$

となります。すると、dp[i+1]という1次元配列（つまりDPテーブルのi+1行目）は、dp[i]という1次元配列（つまりDPテーブルのi行目）と比較して、（全体に| $x_i-x_{i+1}$ |という定数を足した上で） $x_{j+1}$ 番目の要素しか変化していないということがわかります。このように、DPテーブルのi行目とi+1行目が1箇所しか異なっていない場合、インラインDPというテクニックを用いて計算量を減らすことが出来ます。

どうするかというと、まずDPテーブルを愚直に2次元で持つのではなく、1次元で持ちます。そして最初はその1次元配列をDPテーブルの1行目で初期化し、次にその配列の1箇所のみを更新してDPテーブルの2行目を表し、その配列の1箇所をのみ更新してDPテーブルの3行目を表し･･･ということを繰り返していくことで、更新回数がO(Q)回、空間計算量もO(N)でDPテーブルをQ行目まで計算することが出来ます。これがインラインDP（私が勝手に名付けただけですが）というテクニックです。

ただし、その1回の更新では

$\min_{k=1,...,N}dp[k\]+|k-x_{i+1}|$

というものを求めなければいけないので、これを愚直に計算すると1回の更新につきO(N)かかってしまい、全体の計算量がO(NQ)になってしまいます。しかし、これも競プロの問題でよく使われるテクニックで解決できます。これにはまず各k=1,...,Nに対して

$dpl[k\]=dp[k\]+N-k$

$dpr[k\]=dp[k\]+k$

を満たす配列を持っておきます。すると、

$\min_{k=1,...,N}dp[k\]+|k-x_{i+1}|$

$=min(\min_{k=1,...,x_{i+1}-1}dpl[k\]-N+x_{i+1}\:,\:\min_{k=x_{i+1},...,N}dpr[k\]-x_{i+1})$

となるので、配列dpl,dprそれぞれのある連続区間の最小値を求めればよくなります。連続区間の最小値は皆さんご存知のようにsegtreeを用いればO(logN)で求めることが出来るので、1次元配列をそのまま持つのではなく、

$dpl[k\]=dp[k\]+N-k$

$dpr[k\]=dp[k\]+k$

という補正を行ったdpl,dprをそれぞれsegtreeとして持つことで、全体の計算量O(QlogN)でこの問題を解くことが出来ました。このように、この「インラインDP」というテクニックを用いる場合、単純な1次元配列を用いるだけでは解けずsegtreeやBITといったデータ構造を用いる必要があることが多いです。そのため「segtreeを用いたDPの高速化テク」と呼んでる人たちが多いですが、それだともうちょっと指す範囲が広そうなのと、自分はこのテクニックで一番重要なのは

「1次元配列の一部だけを更新していくことによって、実際には2次元であるDPを上から下まで計算できる」

という点だと思っているので、そこを表せそうな「インラインDP」という名前をつけてみました。

最後にこの問題の解答コードを載せます

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144
lint dat[2][N*2+10];
lint inf=1145141919810364364LL;
//[a,b)の最小値
//外からは(a,b,0,0,n)として呼ぶ
lint query(int a,int b,int id,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return dat[id][k];
	lint vl=query(a,b,id,k*2+1,l,(l+r)/2);
	lint vr=query(a,b,id,k*2+2,(l+r)/2,r);
	return min(vl,vr);
}
void update(int id,int k,lint a){
	k+=N-1;
	dat[id][k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[id][k]=min(dat[id][k*2+1],dat[id][k*2+2]);
	}
	return;
}
int x[252521];
int main()
{
	lint sum=0,out=inf,out2=inf;int n,q,a,b;
	cin>>n>>q>>a>>b;x[0]=a;
	rep(i,2) rep(j,N*2+5) dat[i][j]=inf;
	update(0,b,n-b);update(1,b,b);
	rep(i,q) cin>>x[i+1];
	rep(i,q){
		lint dif=abs(x[i]-x[i+1]);
		sum+=dif;
		lint ne=min(query(0,x[i+1]+1,0)-(n-x[i+1]),query(x[i+1],n+1,1)-x[i+1]);
		update(0,x[i],ne-dif+n-x[i]);update(1,x[i],ne-dif+x[i]);
	}
	rep(i,n+1) out=min(out,dat[0][i+N-1]-(n-i));
	rep(i,n+1) out2=min(out2,dat[1][i+N-1]-i);
	assert(out==out2);
	cout<<out+sum<<endl;
}

さて、インラインDPの説明をするためにあえて無視をしていたのですが、この問題を解くためには「全体に| $x_i-x_{i+1}$ |という定数を足した上で」1箇所を更新しなければいけませんでした。StarrySky木などを使えばSegtreeの全体に加算するということも出来ますが、このコードでは全体にいくつ足されたか、という情報をまた別に持っています（ただし、 $dp[x_{i+1}\]$ の最小値を更新する際にその分を考慮しなくてはいけません）これもよく使われるテクニックなので抑えておきましょう。

最後に

さて、この記事は参考になりましたでしょうか。式や図が分かりにくくて理解できないって場合はこの記事のコメント欄やtwitterまでお願いします。出来る限り対処したいと思います。この記事を読んでくれた皆さんが来年以降も競技プログラミングを楽しんでくれることを、そしてこの記事が少しでもお役に立てることを祈りつつ、良いお年を！

コメントを書く

skyaozoraの日記

2017-12-12

「インラインDP」というテクニックに関して

関連問題

最後に