DPとかメモ化再帰とか(2)

Competitive Programming Advent Calendarでtayama0324さんが素晴らしい記事を書いておられました。なので自分もそれに触発されて、以前書いた記事の続きを書いてみました。以下はtayama0324さんの記事を読んでいることを前提に話をします。

DPのメリットとメモ化再帰のメリット

基本的にはtayama0324さんが触れているメリットでつきていると思うんですが、自分は次のようなメリットもあると考えています(本筋から離れるだけなので、tayama0324さんも知っていた上で敢えて書かなかっのだと思います)。

• DPのメリット
  • 配列の再利用でメモリが節約できることがある。
  • データ構造を工夫しての高速化が書きやすい。
• メモ化再帰のメリット
  • 評価が遅延的に行われる。

ひとつずつ説明します。

配列の再利用

これは非常によく知られていることだと思います。配列ではありませんが、フィボナッチ数を計算する以下のコードもメモ化で書く場合に比べてメモリが節約されています。

	int prev1 = 1, prev2 = 1, cur;
	for(int i=2; i<=n; i++){
		cur = prev1 + prev2;
		prev2 = prev1;
		prev1 = cur;
	}
	printf("fib[n] = %d\n", cur);

メモ化でメモリ節約することもやってやれないことはないような気がするんですが自然にはならないと思います。

データ構造を工夫した高速化

dp[n] = dp[n-k]+dp[n-k+1]+...+dp[n-1] + f(n)
みたいな式があったとします(例：ColorfulChain)。これを愚直にやるとO(N*K)かかってしまいます。
しかしこれは、累積和やBITを使うなどしてより高速に計算することができます。これをメモ化再帰でやろうとすると結構大変です(二重再帰で書けばできる)。
似た例として
dp[n] = min(dp[n-k], dp[n-k+1], ..., dp[n-1]) + f(n)
のようなものもあります(例：PrimeCompositeGame要ログイン)。
これまた愚直にやるとO(N*K)ですが、dequeを使ったりmultiset使ったりRMQ使ったりすると計算量が落とせます。それをメモ化再帰でどうやって実現するのかはちょっと自分には分かりません。

評価が遅延的

これをやらないと絶対解けないという状況は見たことありませんが、想定解法より少し悪い計算量だろうけど枝刈りとかで高速化したら通りそう、という状況は結構あります(例えばゲーム木探索でアルファベータ法をやるとか)。こんなときは全ての状態を評価する必要のないメモ化再帰の方が(関数呼び出しのオーバーヘッドを考慮しても)早くなることが多いような気がします。実際にはあまり見たことはないですけど…

メモ化再帰のこだわり

これは宗教というか単なる自分のこだわりの話です。自分はメモ化再帰を書くときはなるべくこの書き方で書く!というのを固定することにしています。

type memo[MAX_SIZE];
bool visited[MAX_SIZE];

type rec(state x){
	//メモ化処理
	if(visited[x]){
		return memo[x];
	}
	visited[x] = true;

	type& ret = memo[x];
        ret = initial_value;

	//基底
	if( ほかのrecを呼び出す必要がない ){
		return ret = 適切な値;
	}

	...
	ret の更新
	...

	return ret;
}

メモ化されているかどうかのチェック

このやり方は大きく分けて二種類の流儀があるようです。一つはmemoに絶対入り得ない値を初期化時に代入しておく方法、もう一つはbool配列ですでに訪問済みか確かめる方法です。
自分は後者の書き方を愛用しています。最大の理由は、前者の方法をとるとき絶対入り得ない値を考えて初期化するのが面倒だからです。bool配列を利用するやり方だと、TopCoderやCodeForcesのように1ファイル1テストケースのとき毎回bool配列がfalseで初期化されているので、初期化処理を書かずにすみます。
visited[x]の更新タイミングについては未だに少し悩んでいます(書き忘れの可能性とか、勘違いしてDAGじゃなかったときにTLEにするかWAにするかどっちがいいのかとか…)。

return 文の書き方

以前は参照変数を使わない

        return memo[x] = ret_value;

という書き方だったのですが、二つの理由からこの書き方はしないようになりました。

1. return 文が複数あるときや、memo[x][y][z]みたいに多次元になっているとき書くのが面倒。
2. xを途中でうっかり書き換えてしまうかもしれない。

基底は特別処理する

これをやるとコードが冗長になってしまう場合もありますが、特別に処理します。理由はうっかり書き忘れてしまうことが多いからです。また、基底の処理はメモ化のチェックより先に書く場合もあります(主にセグフォ対策)。デフォルトでメモ化処理の後にやっているのは、終了条件の判定にコストがかかる場合があるからです。

おわりに

まだ行列累乗とか連立一次方程式とか打ち切りを付与した探索とか色々DP/メモ化再帰に付随した書くネタはありますがそれはまたいつかの機会に。