【C言語】自分がメモ化探索で使っているメモ方法

# メモ化探索とは

1個以上の整数を引数とする関数で再帰的な計算を行う場合、単純にやると同じ計算が何度も走ってしまい、長時間かかってしまうことがある。
しかし、この関数が同じ引数に対しては常に同じ結果を返すのであれば、ある引数の組み合わせについては最初の1回のみ計算を行って結果を保存し、2回目以降に同じ引数の組み合わせで関数が呼び出されたら計算を行わずに保存されている結果を返すことで、計算にかかる時間を減らすことができる。
これを行うと、計算にかかる時間は「1回の計算にかかる時間」×「引数の組み合わせの数」程度になることが期待できる。

## 実例

[D - Bonus EXP](https://atcoder.jp/contests/abc369/tasks/abc369_d) (AtCoder Beginner Contest 369)

<details><summary>解答 (ネタバレ注意)</summary>

「次に倒すかを考えるモンスター」「次にモンスターを倒すと偶数番目になるか」を引数とする関数により計算を行う。

[提出 #57709569 - AtCoder Beginner Contest 369](https://atcoder.jp/contests/abc369/submissions/57709569)

</details>

# 自分が使っているメモ方法

C言語における整数型のグローバル変数は、初期値を明示しない場合 0 に初期化される。
しかし、0 は計算結果としても出てくることが少なくない値であり、メモ用の配列に計算結果をそのまま格納するだけでは、「未計算」と「計算結果が 0」の区別がつかない可能性がある。
そこで、これらを判別できるようにする工夫を行う。

## 計算結果のビット反転を格納する

自分が最もよく使う方法であり、上の「実例」でも用いている。

計算結果の整数をそのまま格納するのではなく、`~` 演算子でビット反転させて格納する。
すると、0 も 0 以外の計算結果も、非零の値に変換できる。
符号なし整数の最大値や、(2の補数を用いている場合) `-1` はビット反転すると `0` になるが、多くの問題では計算結果は必ず非負になり、これらの値は計算結果として現れない。
(これらの値が計算結果として現れる問題の場合は、別の方法を用いる)

ビット反転した結果は、もう一度ビット反転するともとの値になる。

```c
int memo[STATUS1_MAX][STATUS2_MAX];

int calc(int status1, int status2) {
	int ans = 0;

	/* 明らかに計算を終了できる場合を処理する */
	/* (入力列の最後まで処理を行った場合など) */
	/* ... */

	/* メモが記入されている場合、計算結果を返す */
	if (memo[status1][status2]) return ~memo[status1][status2];

	/* 計算を行い、結果を ans に格納する */
	/* ... */

	/* 計算結果をメモに記入し、返す */
	return ~(memo[status1][status2] = ~ans);
}
```

## valid情報を別に持つ

計算結果が実数の場合や、負になることがある場合など、ビット反転での表現が難しいときに用いる。
計算結果の値を格納する配列とは別に、計算結果を記入済かを表す値を格納する配列を用意する。

```c
double memo[STATUS1_MAX][STATUS2_MAX];
char memo_valid[STATUS1_MAX][STATUS2_MAX];

double calc(int status1, int status2) {
	double ans = 0;

	/* 明らかに計算を終了できる場合を処理する */
	/* (入力列の最後まで処理を行った場合など) */
	/* ... */

	/* メモが記入されている場合、計算結果を返す */
	if (memo_valid[status1][status2]) return memo[status1][status2];

	/* 計算を行い、結果を ans に格納する */
	/* ... */

	/* 計算結果をメモに記入し、返す */
	memo[status1][status2] = ans;
	memo_valid[status1][status2] = 1;
	return ans;
}
```

## gen(世代)情報を別に持つ

二分探索中に用いるなど、条件を変えた計算を何度も繰り返す場合に用いる。
valid情報と似ているが、現在何回目の計算を行っているかを表す変数 `gen` を用意し、メモに記入されているのが今回の計算の計算結果かどうかを判定することで、メモに(今回の)計算結果が記入済かを判定する。

メモやvalid情報全体に対し書き込み (初期化) を行わず、変数 `gen` を書き換えるだけでメモの初期化に相当する処理を行うことができるため、初期化のコストが少なくなり、計算時間の短縮が期待できる。

```c
int gen = 0;
int memo[STATUS1_MAX][STATUS2_MAX];
int memo_gen[STATUS1_MAX][STATUS2_MAX];

int calc(int status1, int status2) {
	int ans = 0;

	/* 明らかに計算を終了できる場合を処理する */
	/* (入力列の最後まで処理を行った場合など) */
	/* ... */

	/* メモが記入されている場合、計算結果を返す */
	if (memo_gen[status1][status2] == gen) return memo[status1][status2];

	/* 計算を行い、結果を ans に格納する */
	/* ... */

	/* 計算結果をメモに記入し、返す */
	memo[status1][status2] = ans;
	memo_gen[status1][status2] = gen;
	return ans;
}

int query(int param) {
	/* 計算の条件を (グローバル変数に) 設定する */
	/* ... */

	/* 世代を進める */
	gen++;

	/* 計算を行う */
	return calc(0, 0);
}
```

## メモを記入する位置へのポインタを使う

これまでに紹介した方法と組み合わせて用いる。
関数の引数が多く、添字としていちいち書くのが大変なとき、最初に引数に対応するメモの要素へのポインタを取得し、このポインタを用いてメモの読み書きを行う。

```c
int memo[STATUS1_MAX][STATUS2_MAX][STATUS3_MAX][STATUS4_MAX];

int calc(int status1, int status2, int status3, int status4) {
	int* pmemo;
	int ans = 0;

	/* 明らかに計算を終了できる場合を処理する */
	/* (入力列の最後まで処理を行った場合など) */
	/* ... */

	/* メモが記入されている場合、計算結果を返す */
	pmemo = &memo[status1][status2][status3][status4];
	if (*pmemo) return ~*pmemo;

	/* 計算を行い、結果を ans に格納する */
	/* ... */

	/* 計算結果をメモに記入し、返す */
	return ~(*pmemo = ~ans);
}
```

:::note warn
「明らかに計算を終了できる場合」として引数が負の場合が出てくるときなど、ポインタを「明らかに計算を終了できる場合」の判定を行う前に取得しようとすると未定義動作の原因になる場合があるため、注意すること。
:::

:::note info
逆に、メモの要素数に余裕があり、かつ引数は常に0以上の場合など、「明らかに計算を終了できる場合」であっても問題なくポインタを取得できる場合は、「明らかに計算を終了できる場合」の判定の前に (≒ポインタの変数宣言と同時に) ポインタを取得してもよい。
:::

# おわりに

今回は、メモ化探索において自分が使っているメモ方法を紹介した。
これはあくまで自分が使っている方法なので、使いやすそうだと思ったら真似し、もっといい (書く人に合った) 方法があると思ったらその方法を使えばいいだろう。