Exam Practice

Appearance

コラム: 空間計算量の最適化 (Space Optimization) ​

BSQのDP解法において、最も素直な実装は $O(HW)$ のメモリを持つことですが、実はこれを大幅に削減できるテクニックがあります。

1. 2次元配列は本当に必要か？ ​

DPの漸化式をもう一度見てみましょう。

c
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;

dp[i][j]（現在の行）を計算するために必要な情報は、以下の2つだけです。

  1. dp[i][...] （現在計算中の行の、左側の値）
  2. dp[i-1][...] （1つ前の行の値）

つまり、「2つ前の行」より昔の情報はもう二度と使いません。 したがって、マップ全体と同じサイズの巨大な配列を確保する必要はなく、たった2行分 のバッファがあれば計算は可能です。これにより、空間計算量は $O(H \times W)$ から $O(W)$ に削減されます。

2. さらに削る：1次元配列と変数1つ ​

実は、2行も必要ありません。1行分の配列 と、1つの変数 があれば十分です。

1行分の配列 dp[W] を使い回すとします。 dp[j] を更新しようとしたとき、その中身は「更新前の値（つまり上の行の値）」です。

  • dp[j] (更新前) $\rightarrow$ 上のマス
  • dp[j-1] (更新後) $\rightarrow$ 左のマス

ここで足りないのは「左上のマス」の情報です。更新前の dp[j-1] は、直前のループで上書きされて消えてしまいました。 そこで、prev という変数を導入し、「更新前の dp[j] の値」を一時的に退避させておき、次の列の計算で「左上の値」として利用します。

c
int prev_diag = 0; // 左上の値を保持する変数

for (int j = 0; j < width; j++) {
    int temp = dp[j]; // 更新前の値（次のjにとっては"左上"になる）を退避

    if (map[i][j] == obstacle) {
        dp[j] = 0;
    } else {
        // dp[j]: 上 (更新前なので)
        // dp[j-1]: 左 (更新済みなので)
        // prev_diag: 左上
        dp[j] = min(dp[j], dp[j-1], prev_diag) + 1;
    }
    
    prev_diag = temp; // 退避しておいた値をセット
}

このテクニックを使えば、メモリ消費を極限まで抑えることができます。

まとめ ​

試験（Exam）においては、メモリ制限に余裕があるため、可読性を優先して単純な2次元配列を使うのも正解の一つです。しかし、実務や競技プログラミングのような極限の環境では、このような 「不要な情報の切り捨て」 による最適化が重要になってきます。