The Secret Number (Problem C, 2003 Japan Domestic) [1/3]

大阪工業大学情報科学部内の学生向けにACM/ICPCの勉強会を最近開いています。目標は国内予選突破（まずはね）。その勉強会では主に過去の国内予選の問題を解かせてますが，それらの問題の（僕なりの）解答や解き方をここに載せていこうと思います。

ちなみに今年（2006年度）の公式サイトはこちら。ホストは慶應義塾大学です。過去の問題も載っています。

さて，最初に取り上げるのは"http://www.acm-japan.org/past-icpc/domestic2003/C.htm"。2003年度国内予選のＣ問題です。これは「2次元のマトリックスから最も数字の大きい数字列を探し出せ」という課題。言い換えると，与えられた探索空間から最大値を探す探索問題になります。

真っ先に思い浮かぶのは始点となるノードを探して，そこから再帰で右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, "")

ここでコーディングをする前に計算量を算出してみると，これは上手くいかないことが分かります。この問題の場合，最悪のケースは全てが数字の場合で，その場合の計算量は組み合わせ論的に解析すると，その計算回数は
$\frac{ ( (W-1)+(H-1) )! }{ (W-1)! (H-1)! }$
になります（別の求め方も面白いので次回）。そして問題文には W+H <= 70 とあるので，W = H = 35を代入して求めてみると，計算回数は最悪 $2.8 \times 10^{19}$ 回になって，とうてい解けません。

そこで他の方法を考える必要があります。現状の問題は「考えられるケースを全探索している」ことであり，それによって計算量が爆発してしまっています。こういう場合，一般的には次の手法（考え方）が考えられると思います：

全探索＋枝刈り
全探索＋memoize
動的計画法 (DP: Dynamic Programming)

実際にどれを適用すればよさそうなのかの判断は経験なのですが，結果を言えばここではmemoizeかDPを適用すれば解けます。このエントリではDPで考えて解き，次のエントリではmemoizeで考えてみることにします。

DPというのは，一般的には「最適経路中の部分経路もまた最適経路になっている」性質を利用して解く手法のことを指すようです*1。くだけて言うと，これは確実だという値を求め，その値を土台にして他の確実な値を求めていくということです。グラフ理論の用語を交えて言うと，「ループを1回まわすごとに（少なくとも）1つのノードの値を確定させることで，たかだかノード数分ループを回せば答えが求まる手法」です。

具体的にこの問題にDPを適用してみましょう。最初に解が確定するノードを考えて見ると，次の3箇所のノード（赤色）が該当します（これでループが1回まわりました）：

次に確定できるノードは次の3箇所（赤色）です（これで2回目のループがまわりました）：

これらの赤色のノードは左のノードも上のノードも状態や値が確定しているので，最適値であることが分かります。青色のノードは上は確定していますが左が確定していないので，今回は確定させることができません。

3回目のループをまわすと次のようになります：

そして4回目のループをまわすと次のようになります：

ここで今まで青色だった「4」のノードの値が2314に確定しました。当然94よりも2314の方が大きい数字になるからです。解釈を変えると，再帰による全探索ではこの94という可能性も下の0のノードに伝播させていたわけですが，DPの方法ではその可能性を枝刈りしている，とも理解できます。

ループをまわして変化がなくなったら終了です。そのときに最大値を持つノードの値が答えになります。そしてこの場合，計算量はたかだか O(n) なのです。コーディングはこういう感じになるでしょう：

done[x][y]を初期化（数字ならfalse，非数字ならtrue）

max = ""
continue = true

while continue:
  continue = false
  for x in [0, WIDTH):
    for y in [0, HEIGHT):
      if not done[x][y] and done[x-1][y] and done[x][y-1]:
        field[x][y] = get_max(field[x-1][y], field[x][y-1])
        max = get_max(field[x][y], max)
        done[x][y] = true
        continue = true

次に計算すべきノードをキューに記憶しておくようにすると計算回数が減りますが，この程度であればわざわざそうする必要はないでしょう。これで十分です。

DPのエッセンスは「安心して使える部分解を順次確定していく」ということに尽きると思います。全探索では計算量が大きそうな問題にはDPのアイデアが適用できそうか考えてみましょう。

個人的にはDPはループ（繰り返し）と相性が良い考え方だと思います。次回はこの問題を再帰関数と相性が良いmemoizeで解いてみることにします。

*1:なお，数学的に厳密な議論には興味がありませんので，僕なりの理解で適当な説明をします。あしからず。