病みつきになる「動的計画法」、その深淵に迫る：最強最速アルゴリズマー養成講座（4/4 ページ）

[高橋直大，ITmedia]

今回の問題の解法

　今回の問題のポイントは、ヒントでも挙げた通り、「どうやって途中結果を保持し、無駄な計算をなくすか」です。これさえ気づけるようになれば、この手の問題の考え方は非常に簡単です。

　今回の問題の場合は、「1行または1列ごとに、直前1行のパターンごとの最適な解を保持する」ことが分かれば解けたも同然です。ピンとこない方のために、図を用いて説明します。

　上図のように、上の1行の情報だけ見える状態で、もう1行に情報を追加したとします。このとき、この1行を追加した際に増えた直線の本数は何本でしょう？　こう聞かれた時に、この図さえ与えられれば簡単に答えられるでしょう。

　ここで、1行を追加した際に増える本数を体系化すると、「その行において横棒が引かれた本数」と、「上の行と繋がっていない縦棒の本数」の和だと分かります。ここまで分かれば、「1つ上の行における、縦棒が引かれた場所」に対して、「そこまでの最小本数」を保持することで、動的計画法に落とし込めますね。

　大筋の方針が立ったとしても、実装に悩むかもしれません。これは少し難しいのですが、コンピュータが2進数を使っていることを利用すると、シンプルに実装できます。2進数が判らない方は、0と1のみで整数を表現している、ということだけ分かれば十分ですが、よく分からない場合は検索するなどして少し調べてみてください。

　上図のように線を引きたいとします。縦棒の場所さえ分かれば十分なので、縦棒がある場所を○、縦棒がない場所を×とすると、○××○××○×、と表現できます。この○を1に、×を0に変換すると、10010010となり、さらにこれを10進数に直すと146になります。たったこれだけで縦棒の有無を1行分、1つの整数で表わすことができます。縦棒のすべての組み合わせを調べたいのであれば、図のように横が8マスの場合、00000000から11111111までを調べればよいので、10進数にして0から2^8まで調べるだけで、簡単に全通りを求めることが可能です。

　これは、縦棒を置きたい場所と、障害物があって置けない場所が被っていないかの判定にも役立ちます。コンピュータで2進法を取り扱う際は、ビット演算を覚えると、非常に処理が簡単にできますので、この際覚えてしまいましょう。以下の説明は、すべて2進数で表わした数字での説明です。

	演算子	演算結果	例
and演算	&	両方のけたが1の場合は1に、そうでない場合は0になる	10101 & 10011 → 10001
or演算	|	どちらか片方のけたが1の場合は1に、そうでない場合は0になる	10101 | 10011 → 10111
xor演算	^	両方のけたが同じであれば0に、そうでない場合は1になる	10101 ^ 10011 → 00110
左ビットシフト	<<	指定された数だけけたを左にずらす	00010010 << 2 → 01001000
右ビットシフト	>>	指定された数だけけたを右にずらす	00010010 >> 2 → 00000100（あふれた分は消滅）

　こんな演算どこで使うんだ、と思われるかもしれませんが、今回はこれが大活躍します。例えば、先程と同じように、障害物があるマスを1、そうでない場所を0として、その行の障害物の有無を表現した整数を作るとします。これと、次に置きたい縦棒の場所をand演算して、もし答えが0にならなければ、障害物と縦棒が重なっている、ということが分かります。

　ほかにも、例えばaの7けた目が1かどうか知りたければ、if((a>>6)&1==1)のような条件文を書くことで簡単に判断できます。これを利用して、上1行の縦棒の場所を表わす変数prev、今回置きたい行の縦棒の場所を表わす変数now、今回置く行の障害物の情報field、列数nを用いて、追加しないといけない本数を表わす関数を作ると、以下のように簡単に書くことができます。

public class FloorBoards {
    int addLine(int prev, int now, int field, int n)
    {
        int i;
        int res = 0;
        bool flag = false;  //直前が横棒だったかどうか記憶する
        for (i = 0; i < n; i++)
        {
            if (((now >> i) & 1) == 1)
            {
                if (((prev >> i) & 1) != 1) res++;
                flag = false;
            }
            else
            {
                if (((field >> i) & 1) == 1) flag = false;
                else
                {
                    if (!flag) res++;
                    flag = true;
                }
            }
        }
        return res;
    }
}

　これができれば後は簡単です。上で書いた関数を使って、先程説明したようにソースコードに落とし込むだけで、簡単に答えが導けます。メモ化再帰を使ってももちろん解けますが、今回は動的計画法を用いた解法を示します。

　計算量は、行数をn、列数をmとして、（直前の行のパターン数）×（次の行のパターン数）×（行数）×（列数）=2^n * 2^n * nとなるため、O(n*m*2^2n)となります。n＝10、m＝10のときで1億程度なので、内部の計算が少し重いですが、2秒以内なら十分処理できます。

using System;
using System.Collections.Generic;
using System.Text;
public class FloorBoards {
    public int layout(string[] room)
    {
        int i, j, k, len = room[0].Length;
        int MAX = 99999; //存在し得ない場所に適当に大きな数を入れる
        int[,] dp = new int[room.Length + 1, 1 << len];
        for (i = 0; i <= room.Length; i++) for (j = 0; j < (1 << len); j++) dp[i, j] = MAX;
        dp[0, 0] = 0;
        for (i = 0; i < room.Length; i++)
        {
            int field = 0;
            for (j = 0; j < len; j++) if (room[i][j] == '#') field += (1 << j);
            for (j = 0; j < (1 << len); j++)
            {
                if (dp[i, j] == MAX) continue;
                for (k = 0; k < (1 << len); k++)
                {
                    if ((field & k) != 0) continue;
                    dp[i + 1, k] = Math.Min(dp[i + 1, k], dp[i, j] + addLine(j, k, field, len));
                }
            }
        }
        int res = MAX;
        for (i = 0; i < (1 << len); i++) res = Math.Min(res, dp[room.Length, i]);
        return res;
    }
}

　さて、今回の問題はいかがだったでしょうか？　動的計画法を用いてさまざまな問題が解決できることや、動的計画法と2進数での状態の表わし方の相性の良さは分かっていただけたでしょうか。一見かなり実装が大変そうな問題でも、上手く実装すればこれだけシンプルになりますし、こうしたプログラミング上でのテクニックも徐々に覚えていくと、バグも少なく綺麗なソースコードが書けるようになります。

　今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見いただければと思います。ソーシャルブックマークのコメントでも、筆者個人のブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。

　なお、今回からTwitter用の専用ハッシュタグも用意しました。今回の連載に関するTweetは「#SSAlgo08」をつけてつぶやいていただけばと思います。

　それでは、次回もお楽しみに！

著者プロフィール：高橋直大（たかはし　なおひろ）

Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。2009年に開催された「天下一プログラマーコンテスト」では特別賞を受賞した。現在、慶應義塾大学環境情報学部3年。口癖の「みょんみょん」が聞けるTopCoderニコ生オープン実況もじわじわと視聴者を増やしつつある。

世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから