DPの話 (追記)

Algorithm

前回の記事に対してみやむーさんから素晴らしい反響を頂いたので、こちらにレスポンスする形で追記してみます。

そもそも前回の「DPの話」は、こちらのエントリと内容が全く同じなのでした。全然気付いてなくてごめんなさい・・・。

ループのメリットとメモ再帰のメリット

「メモ再帰のメリットは計算が遅延的に行われること」とのことでした。メモ再帰では、「最終的に求めたい状態には絶対に遷移し得ないノード」への計算は行われません。そのようなノードが数多くある問題では、メモ再帰が速くなりうる。なるほど。

似たようなことがループでは絶対できないというわけではありません。配るDPにおいて、配る元のノードの値が初期値 (最短経路だったら inf とか、経路数だったら 0 とか) のままだったら、配っても意味が無いのでやめる。このような枝刈りを加えると、「初期状態から絶対遷移しないノードから」の計算は行われません。

が、メモ再帰のいいところは、それを特別にコーディングしなくても自然とそうなってくれるところにあります。if 文をいっこ入れないといけないループに比べて、これは明らかなメリットです。

ちなみに、イロモノ要因と思われたBFSによるDPでも、また別の枝刈りを考えることができます。こないだのコイン両替問題のBFS実装にちょっと付け加えましょう。

struct state{ int n, cost; };

int minChange(vector<int> value, int n){
  vector<int> cost(n + 1, inf);
  queue<state> qu;

  for(qu.push((state){0, 0}); !qu.empty(); qu.pop()){
    state st = qu.front();
    if(cost[st.n] <= st.cost) continue;
    cost[st.n] = st.cost;

    if(st.n == n) return st.cost; // ここ！

    for(int i = 0; i < value.size(); ++i){
      if(st.n + value[i] <= n){
        qu.push((state){ st.n + value[i], st.cost + 1 });
      }
    }
  }

  return cost[n];
}

こうすると、答えが見つかった瞬間にBFSが終了するので枝刈りが効いてきます。私がこれを知ったのはLayCurse先生の記事で、私は普通のDPで突撃して死んでいたのでした。

メモ再帰の実装

メモ再帰のメモったよフラグの実装には「メモ変数を nil で初期化」「フラグ専用の変数を作る」の2パターンがあり、みやむーさんはフラグ変数を推してらっしゃいました。私も長いことフラグ変数派だったのですが、

visited[x] = true;

というフラグ立てを忘れるという大失態を一度やらかしまして。nil なら絶対にそんなミスはしようがないので、宗旨変えもアリかなぁと思っています。(普通なら 1TLE で済むのですが、よりによってGCJのLargeでやらかしてしまって満点を逃したという・・・)

DPの話

Algorithm

この記事は Competitive Programming Advent Calendar のために作成されました。

「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、

  • 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない
  • メモ再帰だと書けるけどループだと書けない、またはその逆

とかいう。

この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人としています。

DPとは何ぞや

ナップザック問題のアレとか巡回セールスマン問題のアレとかはDPに基づいたアルゴリズムです。では、DPとは一体何でしょう？この漠然とした質問にうまく答えられないというのが、ダイクストラとか線形計画法とかとは違う、DP特有の疑問なのではないでしょうか。

単刀直入にお答えしましょう。DPとは、DAG上の最短経路を求めることです。

コイン両替問題

のっけから大法螺を吹きましたが、これから詳しく説明していきます。以下の問題を例にとって考えましょう。

Problem Statement
ちょうど n 円のお釣りを払おうとしています。使用できるコインは何種類かあり、i 番目のコインの額面は value[i] で与えられます。
どのコインを何枚使っても構いません。支払うコインの枚数の最小値を計算してください。(常に払えると仮定して構いません)

Method signature
int minChange(vector<int> value, int n)

Examples
0)
  [1, 2, 4, 8, 16, 32]
  63
  Returns: 6
  全てのコインを 1 枚ずつ使います。

1)
  [1, 5, 10, 50, 100, 500]
  324
  Returns: 9
  日本の通貨体系です。

2)
  [1, 4, 9]
  17
  Returns: 3
  4 + 4 + 9 = 17 とするのが最適です。

本質的に同じ問題として AOJ1167: Pollock's Conjecture がありますので、解きたい人はこちらでどうぞ。

この問題をDPで解くとすると、たとえば次のようなコードを書くことになるでしょう。

int minChange(vector<int> value, int n){
  // dp[i] := i 円を払うお釣りの最小枚数
  vector<int> dp(n + 1, inf); // n + 1 個の inf (十分大きな値) で初期化
  dp[0] = 0;

  for(int i = 0; i <= n; ++i){
    for(int j = 0; j < value.size(); ++j){
      if(i - value[j] >= 0){                       // 配列の範囲外チェック
        dp[i] = min(dp[i - value[j]] + 1, dp[i]);  // i - value[j] 円払えるなら、それに value[j] 円を 1 枚足して i 円を払える
      }
    }
  }

  return dp[n];
}

このプログラムは、見方を変えれば DAG*1 上での最短経路を求めているのです。次のようなグラフを考えてみましょう。
n + 1 個のノード (0 ... n の番号を振る) を持ち、任意の j および ノード i について、 ノード i からノード i + value[j] へ有向辺が張られたグラフです。Example の最後のケースを描いてみましょう。

「17円を払う最小の枚数」というのは、「ノード 0 からノード 17 への最短経路」に一致しています (0 - 9 - 13 - 17)。よく見ると、17円だけでなく 1円から16円についても同様であることがわかるでしょう。このように、DPとは最短経路を求めることなのです。

最短経路だけじゃない

「じゃあ、フイボナッチ数を求めるこんなDPがあるけど」

int fib[N];
fib[0] = 1;
fib[1] = 1;
for(int i = 2; i < N; ++i)
  fib[i] = fib[i-1] + fib[i-2];

「これのどこが最短経路なんだね」という突っ込みがあるかと思います。

はい。DP == 最短経路 はちょっと言い過ぎました。このDPでは、最短経路ではなくパスの総数を求めていることになります。

フィボナッチ数の i 項目というのは、つまり 「ノード i - 1 から ノード i に、 ノード i - 2 から ノード i にエッジが張られたグラフにおける、ノード 0 からノード i へのパスの総数」に等しいのです。

もっと言いますと、「...の総数を求めなさい」というDPは、「...というDAGのパスの総数を求めなさい」と言い換えられます。同様に、「...の最小値を求めなさい」は「...というDAGの最短経路を求めなさい」に、最大値は最長経路に言い換えられるのです。

最長経路

最長経路の例も見てみましょう。LIS (Longest Increasing Subsequence) です。

Problem Statement
数列 a から 0 個以上の要素を取り除いて得られる数列を a の部分列 (subsequence) といいます。
与えられた数列の部分列で狭義単調増加 (全ての i < j に対して a[i] < a[j]) であるもののうち、最長のものを求めなさい。その長さを返しなさい。

Method signeture
int LIS(vector<int> a)

Examples
0)
  [3, 1, 4, 1, 5, 9, 2, 6]
  Returns: 4
  このケースに対するLISは複数通りあります。[1, 4, 5, 6] などです。

これは、i < j に対して a[i] < a[j] であるような i, j 間に辺を張ったグラフの最長経路に等しいのでした。O(n^2) です。LIS の計算量は O(nlogn) まで落ちるのですが、今日は遅いDPで勘弁して下さい。


レッツ実装

世の中のDPの問題というのは、大抵次のように分類できます。

これ以外にもあるかもしれません。

そろそろ実装の話に入りましょう。種類はいろいろありますが、やるべきことはどれも同じです。DAG上で最短路/最長路/パス総数etcを求めるには、トポロジカルソートして、トポロジカル順序の小さい順にノードの値を求めていきます。

ノード u[i] から v へ重み w[i] の辺が伸びているとき、v への最短経路長 minCost[v] は minCost[u[i]] + w[i] の最小値。そのまんまですね。グラフの頂点 v に対して、この minCost[v] の計算を、トポロジカル順序に沿って行なっていきます。トポロジカル順序に沿って計算しているのであれば、minCost[v] を求めるときには minCost[u[i]] は既に求まっているはずです。u[i] は v よりトポロジカルに前に来ていなければならないので、当然です。

一般のグラフの最短経路の場合、話はもう少し複雑でした。 こんなグラフがあったとき、

パス a - b - c - d も a - c - b - d もどちらも最短経路になりえる。minCost[b] が分かってから minCost[c] なのか、それとも minCost[c] を求めてそこから伸ばす形で minCost[b] なのか、はっきりしない。だから Dijkstra などという七面倒臭いことをしなければならなかったのです。幸いにもDAGはそうでない。トポロジカルソートできるのだから、b - c と c - b というパスが同時にありえるはずがないのです。a - b - c - d というトポロジカル順序が得られたら、b への最短経路に c が含まれることはない。c への最短経路は a か b から伸ばすしかない。だから頭から順番に計算できる。大変シンプルで良いことです。

トポロジカル順序

ですから、DPときたらまずはDFSを書いてトポロジカルソートしましょう！・・・はい、これは嘘ですね。DPの度にトポロジカルソートしているひとはあんまりいないと思います。現に上のコードもそんなことしてません。でも、さっきのコイン両替問題のグラフをもう一度見てみましょう。

トポロジカル順序など、トポロジカルソートするまでもなく明らかです。ノード 0, 1, 2, ..., n がそのまま答えになっています。それを踏まえてもう一度コードを見てみると、

int minChange(vector<int> value, int n){
  // dp[i] := i 円を払うお釣りの最小枚数
  vector<int> dp(n + 1, inf); // n + 1 個の inf (十分大きな値) で初期化
  dp[0] = 0;

  for(int i = 0; i <= n; ++i){                     // dp[i] をトポロジカル順序 (0, 1, 2, ..., n) の順に訪問して
    for(int j = 0; j < value.size(); ++j){
      if(i - value[j] >= 0){                       
        dp[i] = min(dp[i - value[j]] + 1, dp[i]);  // 直前のノード dp[i - value[j]] から伸ばす
      }
    }
  }

  return dp[n];
}

ちゃんとトポロジカル順序を活用しています。

もうちょっと複雑な例を見てみましょう。巡回セールスマン問題です。

Problem Statement
N 個のノードを持つグラフがあります。辺 i - j 間の重み (正の整数) が graph[i][j] で与えられます
(辺がなければ graph[i][j] には十分大きな値が、graph[i][i] には 0 が与えられるものとします) 。
ノード 0 から出発して、すべての頂点を少なくとも一度訪問するコストの最小値を求めてください。最後にいる場所はどこでもいいです。

Method signature
int travelingSalesmanProblem(vector< vector<int> > graph)

典型的な実装はこんな感じでしょうか。

int travelingSalesmanProblem(vector< vector<int> > graph){
  const int n = graph.size(); // 頂点数
  vector< vector<int> > dp(1<<n, vector<int>(n, inf));  // dp[1<<n][n] := dp[既に訪問したノードの集合][今いるノード] の最小コスト

  // 前処理としての　Warshall-Floyd
  for(int k = 0; k < n; ++k)
    for(int i = 0; i < n; ++i)
      for(int j = 0; j < n; ++j)
        graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

  dp[1][0] = 0; // ノード 0 だけを訪問している状態からはじめて
  for(int i = 0; i < (1<<n); ++i){　  // 「既に訪問したノードの集合」の2進数表現の昇順かつ
    for(int j = 0; j < n; ++j){      //     「今いるノード」の昇順に訪問
      if(i&(1<<j)){                  // ノード j にいて、まだノード j を訪れてない状態 はありえないので弾く
        for(int k = 0; k < n; ++k){  // 次に行くノードに対するループ
          if(!(i&(1<<k))){           // ただし、既に訪問済みだったらやめる
            dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + graph[j][k]); // 更新！
          }
        }
      }
    }
  }

  // dp[全ノードを訪問した][どこでもいい] の最小値を返す
  return *min_element(dp[(1<<n)-1].begin(), dp[(1<<n)-1].end());
}

このDPでは、DAGのノードは (既に訪問したノードの集合 (の2進数表現), 今いるノード) のペアです。このペアの辞書式昇順でループを回して訪問しているのですが、DPが成り立つためには、この訪問順序がトポロジカル順序になっていなければなりません。本当にそうなっているでしょうか。いやそもそも、これってDAGでしたっけ。

ここで注目したいのが、更新式の i|(1<<k) です。2つ目の if で弾いていますので、次にセールスマンが巡回しようとするノード k は未訪問のノードです。つまり、更新の度に 巡回済みのノードの集合 i のサイズはちょうど 1 だけ増えるのです。このDPに対応するグラフ *2 に閉路があったならば、いくらでも更新することができてしまう。でも n 回も更新すれば巡回済みノード集合のサイズは n になって、それ以上更新できない。なので閉路はない。つまりDAGです。

で、k は未訪問であることから、 i|(1<<k) と i を整数として解釈したとき、i|(1<<k) のほうが大きいのも明らかです。 i は昇順にループしていますので、i|(1<<k) が i より先に訪問されてしまうことはない。なので、(既に訪問したノードの集合 (の2進数表現), 今いるノード) の昇順でループを回すと、ちゃんとトポロジカル順序になっています。

配るDP、貰うDP

注意深い人は、巡回セールスマン問題のコードとコイン両替問題のコードがちょっと違うのに気付いたと思います。巡回セールスマン問題の方では、トポロジカル順序で各ノードを訪問したときに、こんなことをしています。

コイン両替では前のノードを見て、コストの最小値をとっていました。しかし巡回セールスマン問題では、次のノードを見て min をとっています。トポロジカル順序を守ってさえいれば、こういうことをしても問題ありません。なぜなら、u[1] を訪れるときには u[1] よりも前のノードを既に訪れているはずだからです。min をとる順番は変わるものの、それによって最終的な計算結果が変わることはないのですね。

俗に、コイン両替みたいなのを「貰うDP」、巡回セールスマンみたいなのを「配るDP」と呼んだりするようです。どちらが優れている、ということはないと思います。書きやすい方で書きましょう。相互に書き換えるのも簡単ですし。

メモ再帰

「DAG最短経路を解くにはトポロジカル順序に沿ってループを回す」と言いましたが、よく知られた解法がもう一つ存在します。話の流れでこんなに後回しになってしまいましたが、全国1,000万のメモ再帰ファンの方々お待たせしました。メモ再帰です。

ループ解法がボトムアップ型なのに対し、こちらはトップダウン型と言えるかもしれません。貰うDPをそのまま再帰で書き表し、ついでにメモ化すればメモ再帰の完成です。

const int nil = -1;  // 未計算であることを示す値
vector<int> memo;
vector<int> value;

int rec(int n){
  if(n == 0)   // 再帰の終了条件
    return 0;

  if(memo[n] == nil){　// もし未計算だったら
    int result = inf;
    for(int i = 0; i < value.size(); ++i){
      if(n - value[i] >= 0){
        result = min(result, rec(n - value[i])); // 貰うDP
      }
    }
    memo[n] = result;  // そしてメモ
  }

  // 計算済みなら即座に memo[n] の値が返される
  return memo[n];
}

int minChange(vector<int> __value, int n){
  memo = vector<int>(n + 1, nil);  // メモの初期化
  value = __value;                 // めんどいのでグローバルに持って行きます
  return rec(n);
}

配るDPをメモ化でやってやれないことも無いと思うのですが、貰うDPのほうがずっと直感的です。貰うDPですから、メモ再帰も「トポロジカル順序に沿って埋めていく」戦略であることには変わりありません。

優劣比較

ループとメモ再帰、どちらが優れているでしょうか？両方とも広く使われていることからも分かるように、あまり大きな差があるわけではありません。特に、どちらも時間計算量 O(V + E)、空間計算量 O(V) と、計算量ではイーブンです。それぞれのメリットを強いて言うならば、

ループのメリット:

  • コード長が短い (一般的な傾向として)
  • 関数呼び出しのオーバーヘッドが無いので若干早い
  • 深い再帰によるスタックオーバーフローのリスクがない

メモ再帰のメリット:

  • トポロジカル順序を知らなくても直接適用できる

メモ再帰のメリットについては説明が必要でしょう。コイン両替問題のループ版では、0, 1, 2, ..., n がDAGのトポロジカル順序だと見切った上で、その順番で dp[i] についてループを回さなければなりませんでした。一方、メモ再帰ではそんなことお構いなしに、ただ貰う部分だけをコーディングしています。この「トポロジカル順序を意識しなくても、貰う部分だけを書けば動く」というメリットは、例えば範囲DP (配列 a に対して、その部分列 a[left .. right] に対する解 dp[left][right] を求めていくタイプのDP)　のような、トポロジカル順序が見えづらい問題に対して大きな威力を発揮します。私は、そのような問題に対してはメモ再帰を、トポロジカル順序が明らかな問題に対してはループを使うことにしています。コード長が短いほうが好きなので。

ループではトポロジカル順序を意識する必要があって、メモ再帰では必要ない、それでいて計算量も同じというのは、不思議な感じがするかもしれません。これは、メモ再帰という操作がトポロジカルソートを暗に含んでいる為です。トポロジカルソートの典型的な実装はDFS、つまり再帰なのでした。この計算量も O(V + E) なので、定数倍としてメモ再帰の中に消えてしまうのです。

何にせよ、ループで解けてメモ再帰で解けない、あるいはその反対のような、時間/メモリ制限がタイトな問題はあんまり目にしません(そもそもそんな問題は作りにくいです)。両方使いこなせるようになった上で、書きやすい方を選ぶのがいいでしょう。

ところで、このループ版のみを DP と呼び、メモ再帰とDPを明確に区別している人もいるようです。一般的にどう捉えられているのかは知りませんが、個人的には区別する必要は感じません。解くべき問題をDAGの最短経路問題などに落とすこと、それをトポロジカル順序で埋めていくことで解くことにDPの本質があるのであって、どのように実装するかは瑣末であるように思うのです。あくまで私の独自解釈ですが。

普通に最短経路で解く

DAGの最短経路に落ちるのであれば、普通の最短経路アルゴリズム、つまりダイクストラでも解けて当然なはずでゲソ。コイン両替問題をダイクストラ・・・は面倒なのでBFSで解いてやろうじゃなイカ。

struct state{ int n, cost; };

int minChange(vector<int> value, int n){
  vector<int> cost(n + 1, inf);
  queue<state> qu;

  for(qu.push((state){0, 0}); !qu.empty(); qu.pop()){
    state st = qu.front();
    if(cost[st.n] <= st.cost) continue;
    cost[st.n] = st.cost;

    for(int i = 0; i < value.size(); ++i){
      if(st.n + value[i] <= n){
        qu.push((state){ st.n + value[i], st.cost + 1 });
      }
    }
  }

  return cost[n];
}

はいできた。この実装でも、トポロジカル順序を意識することなくコーディングできてしまっています。そういえばトポロジカルソートのもう一つの典型的な実装に、「入次数 0 のノード (とそこから伸びる辺) をひたすら取り除きまくる」というものがありましたが、あれはBFSするとさっくり実装できそうな感じでしたね。

最短経路以外

最短経路DPばっかり見てきて、最長経路や経路総数のDPがおろそかになっていました。が、最短経路が分かれば他のも簡単です。最短経路の更新式は、 min(minCost[ u[i] ] + w[i]) みたいな感じでした。足し算でコストを求めて、min をとる。

min を max に変えて、max(maxCost[ u[i] ] + w[i]) とすれば最長経路です。

確率DPはちょっと違って、 sum(probability[ u[i] ] * w[i]) といったところ。

経路総数は辺に重みが無いので sum(numPath[ u[i] ]) ですが、重みが無いのではなく、重み 1 固定と捉えると、 sum(numPath[ u[i] ] * w[i]) となって、確率DPと同じ式が出てきます。こうしてみると、色々あったはずのDPのパターンが大抵似たり寄ったりになってしまいました。

しかしながら、聡明な皆さんはさらなる共通した性質にお気付きのことでしょう。

  • 最短経路は + と min
  • 最長経路は + と max
  • 確率DPは * と +
  • 経路総数も * と +

　　min(x+z, y+z) = min(x, y) + z

まだわかりにくいので、min(foo, bar) のことを演算子で書くことにします。 foo▼bar で最小値を表すという記法を導入。書き直すと…

　　(x＋z)▼(y＋z) ＝ (x▼y)＋z

これは、分配法則です。記号が違うだけで、足し算と掛け算の分配法則 (x×z) ＋ (y×z) ＝（x＋y） × z と全く同じ形をしています。

「Ａ地点からＣ地点の最短経路」という条件を文字通りに書くと (x＋z)▼(y＋z) つまり全部の可能な経路を作ってみて最小値を取る、 という計算になりますが、等式をみたら最適化のチャンス！ min と ＋ の分配法則によると、 (x▼y)＋z つまり、代わりにまず落ち着いて途中までの最短路 (x▼y) を計算してから、 +z じっくり経路を延ばす、という計算法でも正しく答えが求まるわけです。 というのがダイクストラ法であり、ウォーシャル・フロイド法です。

さっきは、引き算の裏に結合法則の成り立つ足し算を見出して並列化をしました。 同じように、素直に書いたプログラムの裏に分配法則が潜んでいないか考えるのも重要です。 分配法則を使って高速な計算をするアルゴリズム導出法はあまりにも重要なので名前がついていて、 動的計画法 といいます。 競技プログラマーさんにはおなじみでしょう。

Derive Your Dreams - 計算のきまり

分！配！法！則！です！DPにまつわる各種演算は、+ と min であることや * と + であることが重要なのではなくて、分配法則が成り立つことが本質的に重要なのです。この記事は目からウロコでした。

DP問題の難しさ

さて、DP問題はDAG上の何かに帰着できる、という話をしてきました。コイン両替問題ではこのDAG構造は比較的見えやすいのですが、巡回セールスマン問題では、(既に通過した頂点の集合, 今いる頂点) という非自明なもの (経験を積んだ競技プログラマにとっては自明かもしれませんが) を持ち出さなければDAGに落とせませんでした。与えられた問題に対して、どんな状態空間を、どんなDAGを考えればよいのでしょうか。

これは非常に難しい質問です。逆に言えば、世の中のDPの問題は、まさにこの部分をプログラマに問うているのです。これに答えるためには、与えられた問題に対する深い洞察が必要です。愚直に状態空間を考えると爆発的に大きくなるけれども、問題特有の性質をうまく使うとそれが小さく抑えられる、というのがDP問題を解くときの非常に典型的なシナリオです。

まぁ、「それができたら苦労はせんわな」的な結論で終わるのもアレなので、それでもたまに役立つかもしれない DP tips をご紹介して終わりにしたいと思います。

状態空間以外を問うDP

DP問題というのは状態空間を考えさせるのが本質だと言いましたが、少数ながら例外もあります。AOJ1056: Ben Tohは 100,000 ^ 2 の状態空間が一瞬で見えるタイプのDPですが、アルゴリズム的な工夫によって空間を減らすのではなく、「ほとんどの状態はすごく小さいから 0 で近似できるよね」と言いながら計算をサボる問題でした。手前味噌ですが、私が作った問題の中でもお気に入りの一つです。同様の近似を要求する問題としては、AOJ2268: 乱択平衡二分探索木があります。hos' Xmas Contest 2010: Presentsも似たような話で、状態空間の多くが exactly 0 になることを解析的に示すことができて、計算をサボれる。

DAGにならない場合

問題を自然にグラフに落としたとき、ちょうどいいサイズのDAGになればいいのですが、DAGにならない場合もあります。その場合はどうしたらいいか。

最長経路や経路総数DPでは、そもそもそんなことが起きないことが多いです。というのも、DAGにならなければ最長経路や経路総数は無限大になってしまうので、「最大値を求めよ」という要求が無意味になってしまうからです。それでもしっかり問題として成立させている稀有な例がAOJ2307: Palindrome Gerenatorです。さすがwata先生。

確率DPや期待値DPでは、DAGに限りなく近いグラフが登場することがあります。DAGにring (両端の頂点が同じであるような辺) がくっついたようなものです。AOJ2236: スプリング・タイルとかですね。ring は簡単な式変形によって取り除けて、そのまま普通のDPになるのが定番です。DAGからは程遠いグラフになる期待値の問題がStrange Coupleです。この問題は期待値の関係式を書き下すと線形連立方程式に落ちるので、ガウスの消去法にでも放り込んでおしまいです。

最短経路が一番わかりやすくて、ダイクストラでもすればよろしい。AOJ1150: Cliff Climbingとか、いわゆる拡張ダイクストラとか呼ばれる類の問題です。また、計算量さえ許せば、次元を増やして強引にDAGに持ち込むことも出来ます。普通の (DAGに限らない) 最短経路問題をDPで解いてみましょう。

N 個のノードを持つグラフがあります。辺 i - j 間の重み (正の整数) が graph[i][j] で与えられます 
(辺がなければ graph[i][j] には十分大きな値が、graph[i][i] には 0 が与えられるものとします) 。
ノード 0 から出発して、ノード N - 1 に到達する最小コストを求めてください。

Method signature
int shortestPath(vector< vector<int> > graph)
int shortestPath(vector< vector<int> > graph){
  const int n = graph.size();
  vector< vector<int> > dp(n, vector<int>(n, inf));

  dp[0][0] = 0;
  for(int t = 0; t < n - 1; ++t){
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < n; ++j){
        dp[t+1][j] = min(dp[t+1][j], dp[t][i] + graph[i][j]);
      }
    }
  }

  int result = inf;
  for(int t = 0; t < n; ++t)
    result = min(result, dp[t][n-1]);
  return result;
}

dp[t][i] := ちょうど t 回の移動でノード i に移動する最小コストを求めていくDPです。t からは t + 1 にしか移動しないので、これでちゃんとDAGになりました。頂点数 N のグラフで、最短経路の長さが N - 1 を越えることはないので、そこまで調べれば十分です。(result の線形探索も本当はいらないんですが、分かりやすさのために残しときます。) ダイクストラに比べて時間もメモリもバカ食いしてますが、こんなシンプルなのも乙なものでしょう。

ところで、 O(n^2) もメモリを食うのは贅沢です。これをケチって1次元にしてしまい、dp[t][i] が必要なときはいつでも dp'[i] を使うようにしてしまいましょう。これは元のプログラムとは違うものを計算していますが、それでも最終的に最短経路はしっかり求まってしまいます。というのも、こうすると dp'[i] は常に dp[t][i] 以下になるけれども、「任意回の移動でノード i に移動する最小コスト」を下回ることはないからです。こうやってメモリ O(n)、 時間 O(n^3) の最短経路DPが生まれました。このアルゴリズムには既に名前がついていて、Bellman-Ford といいます。

終わりに

「DPは特殊技能」という言葉が一昔前のICPCerの間で囁かれていたそうです。それだけDPには典型的な思考法が存在せず、そのアルゴリズムの設計は各人の経験知によるところが大きかったのでしょう。今でも一つのDPの問題やアルゴリズムを取り上げて解説した記事はいくらでもありますが、あらゆるDPアルゴリズムにあまねく共通する性質を掘り下げたものは多くありません。

この記事では、DPとDAGの関係性について着目して解説しました。結果として、ループやメモ再帰といった実装上の些細な問題で躓かないようになり、その問題特有の性質についてより深く考察できるようになることを目標としました。DPとDAGの関係性を大きく取り上げた記事を私は他に見たことがなく、このDPの解釈がどこまで通用するかはよく分からないというのが本音だったりします。RedCoderの方々はDPをどのように捉えているのでしょうか。いろんな人のブログを見る限り、DAGというのはそれほど外していないように思うのですが。

最後に、この記事は眠気の中で勢いで書かれました。大嘘こいてるかもしれません。特にソースコードはコンパイルすら通してないので、バグってたらごめんなさい。疑問質問はコメントにて受け付けます。

それでは、Happy Dynamic Programming!

*1: 有向 (Directed) で閉路を持たない (Acyclic) グラフ (Graph)

*2:巡回セールスマン問題として与えられたグラフ graph と DPするときに考えるグラフ dp がごっちゃになりやすいですね・・・。すみませんが頑張って解釈してください

パソコン甲子園2011 本戦

Contest

2日間ボランティアとして働いてきました。選手・スタッフの皆さん、お疲れさまでした。

さて、プログラミング部門の第 6 問が物議を醸しています。

が、今回取り上げるのは第 5 問の方です。Twitter 等ではこの問題に対する参加者のコメントはあまり見受けられませんが、この問題もまた不備な点が指摘されています。

この問題の題意は、「ロボットアームの回転命令が入力されたとき、回転後のアームの先端の座標を出力せよ」というものです。アームの挙動や回転命令の他に、出力すべき座標の計算方法も問題文に与えられていて、選手は要求の通りに計算するプログラムを書くことが要求されます。(問題文はまだ公開されていませんが、選手の他、会場でも若干の配布があったようです。残念ながら今私の手元にはないので、このような説明でご容赦ください)

この問題の不備な点は、文中に「行列 A と 位置ベクトル b の積を計算する」というような記述があり、A と b そのものは明確に定義されていますが、行列とベクトルの積とは何なのかという説明が一切無い点です。高校数学では行列は 数学C で扱うはずですが、選手の中にはまだ 数学C を履修していない者もいます。実際に何人かの選手と話しましたが、まさにこの点が理解できず、この問題を解くことを諦めたという声が複数人から聞かれました。

全ての選手が行列を知っているわけではないことは明らかですから、その定義については問題文中で厳密に説明すべきだったでしょう。

反論

これについて、次のような反論が考えられます。「例えばダイクストラ法なども高校教育の範囲ではない。要求する知識を高校一年生の水準に限ることは作題の上で非常に大きな制約になり、現実的にコンテストを開くことが不可能になる。従って、選手が受けている教育のレベルを越える出題も許容されるべきだ。」しかしながら、この主張は的を射ていません。以下にさらなる反論を述べます。

ダイクストラ法を使わないと解けない問題は、ダイクストラ法を知らないと絶対に解けないのでしょうか？そんなことはありません。ダイクストラ法と同じアルゴリズムを一から組み立て、正当性を証明すればよいのです。ハンガリアンマッチング、Suffix Array、どんな難しい既知のアルゴリズムやデータ構造を使う問題であっても、また選手がそれを知らなくても、十分に賢ければ、自力でそれを再発明して解くことができます。それが現実的かどうかはともかく、解くチャンスは与えられています。

一方で、この問題における行列とベクトルの積は「定義」です。行列を知らない選手が、行列のベクトルの積としてどのような解釈を考えたとしても、その解釈がどれほど合理的であっても、その解釈が正しいと確信する手段はありません。手当たり次第にプログラムを書いてみて、運良く正しい解釈に沿ったプログラムを書けていれば正解、というギャンブルを強いられます。教科書や参考書を見ればすぐに分かることではあり、実際に書籍の持ち込みは許可されていますが、不運にも持ち込んでいなければお手上げです。インターネットの利用は許可されていないのです。

問題を解くにあたって、高校の範囲を越えた知識を要求することは構わないでしょう。しかしこの問題では、題意を理解するにあたって、多くの選手が持っていない知識を要求しています。これは問題の不備であり、ミスジャッジと呼ぶべきです。題意を理解するまでの段階において、選手間の大きな不公平は存在すべきではありません。問題文は、中学卒業程度の学力と、基本的なプログラミングの知識があれば理解できる程度に詳しく書くべきです。

第 6 問は問題文が曖昧でしたが、これは全ての選手に等しく不利益を与えるものでした。一方この問題は一部の選手に著しい不利益を与えるものであり、競技の公正性という観点からは、第 6 問よりもむしろ性質が悪いと捉えることも出来ます。

さらに反論

この主張をメールで送ったとして、いかにも作題委員の返答しそうな主張を先回りして潰しておきます。

  • 主張: 問題の解釈も競技の一部である。選手は問題文の解釈に困らないように、あらかじめ十分勉強すればよいだけのことだ。
    • 反論: それはパソコン甲子園の趣旨に合致するのか。逆にプログラミング能力を競い合うことを妨げていないか。

全国の高校生及び高等専門学校生などが、情報処理技術における優れたアイディアと表現力、プログラミング能力等を競い合うことにより、生徒自身のスキルアップを図るとともに、情報化社会を支える人材の裾野を広げることを目的として開催します。

パソコン甲子園2011 - 概要 - 趣旨
  • 主張: 行列やベクトルを利用した座標の計算方法は、問題の定義そのものではなくヒントにすぎない。アームの挙動や回転命令までが定義であるので、座標の計算方法は、選手が十分に賢ければヒントを無視して再発明することができたはずだ。
    • 手元に問題文が無いので精査できないのですが、問題文は「ロボットアームを作りたい太郎君が書いたメモを参考に、座標を計算せよ」のようなストーリーになっていました。「参考にせよ」とは言いましたが、「メモの通りに計算せよ」とまでは言ってなかったかもしれません。仮に「指定された式を使わなければならない」という題意でないのなら、その式が全員にとって理解できるものでなくてもミスジャッジとまでは言えないでしょう。
    • しかしながら、それでは選手が考えるべきアルゴリズムに対して、ヒントの割合が極めて大きいように思います。一部の選手に著しいヒントを与えるものは、ミスジャッジではないにせよ、回避されるべき問題でしょう。

雑記

とにかく今年の件で分かったが、ぼくがパソコン甲子園に3年間出場して学んだ唯一のことは「パソコン甲子園で問題を解いているときに詰まって、何が悪いのかわからないという状況に陥ったとき、間違っているのはぼくらではなく必ずパソコン甲子園側だ」ということだった。

PCKと同じく高校生以下対象のSuperConや情報オリンピックに比べ、PCKはより初心者を対象としている点で初心者がこういう大会に参加するきっかけを作るには素晴らしいものであるし、そもそも競技人口が少ない中で同年代の同じことに興味を持つ人達と交流できる貴重な機会としてたいへん価値のあるものだと思っている。

そんな素晴らしい機会にぼくが学んだことがあんなことだというのが残念でならないし、同じように思う人が今後は絶対に現れてほしくないと思う。

パソコン甲子園2011本戦 プログラミング部門 - Wrong Answer -- japlj - TopCoder部

今年でパソコン甲子園は9年目だが、私が何らかの形で関わりだしてからは8年目になる。2004, 05 はプログラミング部門の選手として参加し、会津大学に入ってからはボランティアとして運営に携わってきた(一度だけボランティア募集の告知をうっかり見落として、ただの観客として参加した年があったが)。

ボランティアとして参加して、初めて見えてくることもある。パソコン甲子園のスタッフは、皆素晴らしい人ばかりだ。

ここにパソコン甲子園の支援機関の一覧がある。協賛・支援機関はざっと 50 ほどだろうか。これはICPC福岡大会のWebサイトにある企業ロゴの数のざっと3倍だ。このご時世だ、賞金や賞品にも見られるように、予算は年々厳しくなっているのだろう。一社でも多くのスポンサーの理解と協力を得たいという事情は想像に難くない。

多くの人が絡めば絡むほど、多くの人の思惑がもつれていく。会津大学は、プログラミングやコンテンツの創作に秀でた高校生の獲得に繋げたいことだろう。協賛企業は、せっかく協賛金や賞品・懸賞品を提供しているのだから、自社の宣伝をしたいに違いない。市や県などは、情報教育に力を入れていることを市民に広くアピールしたいはずだ。運営側は、何重もの板挟みの中で、誰からも不満が出ないように調整しなければならない。会津大学のPRのために、選手は大学見学に案内される。今年は協賛企業の2社が自社の紹介をする場が設けられた。より多くの市民に会場まで脚を運んでもらうために、著名人に審査や講演を依頼し、駅前や街中でビラ配りまでしている。

人が集まれば集まるほど、無事にイベントを運営するのは難しくなる。ICPC に参加するのは選手とコーチとスポンサーぐらいなものだろう。参加も見学もしたことはないが、情報オリンピック、SuperCon、Epochまつやまなども同様ではないだろうか。一方パソコン甲子園には子供から老人まで、一般の観客が観戦に来るのだ。コンピュータに詳しくない一般の観客にも、楽しんで帰ってもらわなければならない。事故なんてもっての外だ。ボランティアやスタッフには一人一部運営マニュアルが手渡される。その量は数百ページに及び、全てのスタッフとボランティアのスケジュールが記述され、各人の仕事内容から緊急時の対応、例えば落し物の管理・迷子や傷病者の応対などにも配慮が行き届いている。

傍から見ているだけでも、大変な労力であることはわかる。運営本部は深夜12時頃まで明かりが付いていることも珍しくないし、あるスタッフの女性などは「私ここ2週間4時間睡眠ですよ」とのことだった。

スタッフの方々の本来の仕事は、会津大学の職員である。パソコン甲子園の運営は彼らの仕事の一つにすぎないし、彼らはプログラミングやデジタルコンテンツ、モバイルの専門家ではない。だからどの部門の審査にも彼らは携わらず、それぞれ独立した審査チームがいるのだ。

誰だったかよく覚えていないが、デジタルコンテンツ部門の選手と思われる高校生が、「審査環境を Internet Explorer に限ることを止めるべきだ」と主張しているのを最近目にした。そんなに声高に叫ぶ必要はない。喧嘩腰になる必要もない。ブラウザに明るくない人でも問題点を理解できるようにまとめ、ただ代表宛てにメールを送れば良い。私はどのスタッフがそのメールに応対することになっているか知っている。彼らは信頼できる人たちだ。彼らが問題点を認識できれば、適切な判断を下せる人、上役ないし審査チームに届けてくれるはずだ。そうなれば、来年からは改善されるだろう。

審査チームが適切に対応すれば、だ。プログラミング部門で今起きているのは、そういうことなのだと思う。

ここ数年のプログラミング部門審査チームは、あまりにも問題を起こし過ぎ、またその対応を誤り過ぎている。題意の不明瞭な問題は増加する一方だ。ジャッジデータの改行コードが LF であるべきところ CR + LF になっていて、 std::cin を使った選手のコードは正しく入力を読み込まなかったこともあった。驚くべきことに、これは選手からの指摘によって公知となった。ジャッジデータは非公開である。彼はたった3時間のコンテストの間に、間違いと判定された自分のプログラムがやはり正しいと確信し、ジャッジデータに CR が入っているのではと疑い、実際にそれを証明してみせた*1　*2。彼は即座に修正を求めてメールを送ったが、対応は拒否された。ひどい話だ。彼は scanf に書き換えてこの問題に正解したそうだが、これを知らずに不正解とされたまま終わった選手がどれだけいただろうか。

別の例を挙げると、今年度の予選は台風で多くの高校生が参加できず、彼らのために再予選が行われたが、その問題は過去のパソコン甲子園の問題そのままであった。過去問は Aizu Online Judge にて誰でも読み放題解き放題になっているにもかかわらず、だ。

私にはミスジャッジを責める資格はない。私自身、数多くのミスジャッジを犯してきている。よりによってこのパソコン甲子園の翌日に、OB会の模擬地区予選でやらかしたばかりだ(この問題は私の担当であり、文責は私にある。iwiwiさんの指摘はまったくもってその通りで、この場を借りてお詫びします)。

作題経験者ならば理解できることだが、ミスジャッジを完全になくすのは到底不可能なことである。しかし、パソコン甲子園のような頻度は度を越している。私にとって許せないのは、ミスジャッジそのものではなく、審査チームがどうやらミスジャッジを犯しやすい態勢にあるらしく、しかも一向にそれが改善される気配を見せないことだ。

会津大学には ICPC Programming Club という団体があり、顧問をしていらっしゃる教員は Aizu Online Judge を開発・管理しているその人だ。メンバーには数百問から千問以上を解いた人も少なくないし、そういった人たちは何千問もの問題を読んできている。読みやすい問題とはどんな問題かをよく分かっていて、また UAPC などのコンテストの開催経験、作題経験もある。私たち (私もメンバーの一人だ) に助言を求めていれば、前もって第 5 問のような指摘はできたはずだ。機密保持等の観点で学生にそのような仕事を任せられないというのなら、顧問の先生に頼めば良いだろう。彼もかつての ICPC 上位入賞者で、作題経験もあるのだ。

ちなみに先生は、パンフレットの審査チーム紹介のページに名前と顔写真が載っている。が、「審査チーム」と称する枠の外側に彼はいて、いったいこれはどういう意味なのだろうか？本人にお聞きしたが、彼は確かに審査チームの一員ではないということだった。ならば何故彼が載っているのだろうか？

JAPLJさんから上のような意見が聞かれたのはとても悲しいことだ。運営スタッフは、パソコン甲子園を成功させるために毎年血の滲むような努力を、睡眠や食事さえも削っての作業を続けている。審査チームの行為は、その努力を一手でひっくり返すことに他ならない。スタッフがJAPLJさんのエントリを見たら、何を思うだろうか？私はこのエントリに対して、何ら反論の言葉を持たない。スタッフの心中を察する度に、やりきれない思いになる。

審査チームは猛省しなければならない。そして、今の審査チームにコンテストを開催する力量があるのかは極めて疑わしい。根本的な対策がなされる必要がある。

*1:競技プログラミングを知らない人のために言うと、ジャッジデータを盗み出すなどの不正行為をしなくてもこれは可能である。選手のプログラムが間違いであったときに、その原因が異常終了によるものか、時間制限超過なのか、出力の間違いなのかといった情報が与えられるので、これを元に入力データについて1回の提出当たり 1 - 2 ビットの情報を得られる。

*2:ちなみに、彼は私の母校の後輩である。まったくもって誇らしいことだ。

計算機クラスタ構築メモ

Misc

計算機クラスタを構築することになりました。

私の研究室には数値シミュレーションのための計算機クラスタがあるのですが、数年に渡る使用の結果、パッケージやライブラリの管理が煩雑になってきました。正確に言えば、今までまともに管理してこなかったツケがそろそろ回り始めてきました。業を煮やして「もうOSごと再インストールしてしまおう」ということになりまして、その役目を私が仰せつかったわけです。

「後学の為に作業メモをWikiにまとめといてね」と頼まれましたが、研究室Wikiとかまだないのでまずはこちらに。

ちなみに、再インストールのサポート料金の見積もりも前もって業者にお願いしていました。高かったです。

続きを読む