The Secret Number (Problem C, 2003 Japan Domestic) [3/3]
2003年度国内予選の "http://www.acm-japan.org/past-icpc/domestic2003/C.htm" 問題の解説の第3回目です。
第1回目はこれをDP（動的計画法）で解き，第2回目はmemoize（メモ化）の説明を行いました。今回はmeomizeを用いたメモ化探索で本問題を解いてみましょう。
第1回目での全探索法は次のようなアルゴリズムでした：
真っ先に思い浮かぶのは始点となるノードを探して，そこから再帰で右or下に数字があれば連結していくという手法。コーディングはこんな感じ（記法はPython-likeな適当言語です）：
def rec(x, y, string): string += field[x][y] if stringがmaxよりも大きければ: max = string if 右が数字: rec(x+1, y, string) if 下が数字: rec(x, y+1, string) max = "" for x in [0, WIDTH): for y in [0, HEIGHT): if field[x][y]が数字 and 左が非数字 and 上が非数字: rec(x, y, "")
これを逆にして，「数字列の終点となるノードを探して，そこから再帰で左or上に数字があれば連結していくという手法」を考えます。これは前のものと大差ないように思えますが，意外と異なっています。Python-likeな記法でコードを示します*1：
def rec(x, y):
if x < 0 or y < 0 or field[x][y]が非数字:
return ""
else:
return get_max( rec(x-1, y), rec(x, y-1) ) + field[x][y]
max = ""
for x in [0, WIDTH):
for y in [0, HEIGHT):
if field[x][y]が数字 and 右が非数字 and 下が非数字:
value = rec(x, y)
max = get_max(max, value)関数型言語に慣れている方は，こちらの方が見慣れている書き方でしょう。再帰関数 rec() は非常にシンプルです（C言語で書けばこんなにシンプルには見えないでしょうが）。
このアルゴリズム自体は，始点から始める場合と同じく，全てのノードを探索します。しかし，ここで重要なのは，再帰関数 rec() は必ず値を返しており，その値が実際に求める値（終点ノードを固定した場合の最大の数値列）になっているということです。また，引数以外の外部状態には依存せずにその関数の値が求まることも分かります。ですから，この関数はmemoizeできます（詳しくは前回を参照）。
ここではmemoizeの実装は非常に簡単で，次のように数行書き換えるだけです：
def rec(x, y):
if x < 0 or y < 0 or field[x][y]が非数字:
return ""
else:
if cache[(x, y)]が存在しない:
cache[(x, y)] = get_max( rec(x-1, y), rec(x, y-1) ) + field[x][y]
return cache[(x, y)]
max = ""
cache = {}
for x in [0, WIDTH):
for y in [0, HEIGHT):
if field[x][y]が数字 and 右が非数字 and 下が非数字:
value = rec(x, y)
max = get_max(max, value)追加・変更することはたかだか (1)キャッシュの初期化，(2)キャッシュが存在すればキャッシュを返す，(3)値が求まればキャッシュに保存する，ということだけで，これはアルゴリズム自体に深入りすることなく，単純な置き換えで実現します。
このアルゴリズム自体は，memoize前と変わらず基本的に全探索を行います。しかし，この問題の場合，全探索のパス上に同じ探索経路が非常に多くあります。その同じ探索経路がmemoizeで省かれることによって，計算量が激減して問題が解けるようになるのです*2。
ところで，このmemoize版アルゴリズムと前々回のDP版アルゴリズムの計算量は等しいはずです。というのも，実はどちらとも「ノードの値が確定すればそれを記憶し，再度計算し直さない」ことを行っているだけなのですから。
