最強最速アルゴリズマー養成講座：細かすぎて伝わりにくいTopCoderのコーディングスキル向上マジック (3/3)

解法

　マスの数は最大で1000*1000の100万個ありますので、すべての石の入れ方は、条件を満たさないものまで入れると2の100万乗になります。これでは、通常の探索では時間がかかりすぎますね。よって、どのように置けばよいのかを見つけない限り、この問題を解くことはできません。

　そこで、まずは適当に石を置いて、どんな風になるかをシミュレートしてみましょう。TopCoder形式の関数を使ったまま、標準入出力を使って可視化をしてみましょう。まずは、適当に左上から詰めてみます。

　ここでは、実際の盤面のサイズより、上下左右に2マス分ずつ広くなった盤面を想定したプログラムを作成しています。こうして、実際には存在しないデータを配置することで、端での例外処理を行わずにスムーズにプログラムが動くようにすることができます。こうしたテクニックを番兵法と呼びます。番兵法はさまざまな場面で使うことが可能で、メジャーな例を挙げれば、C言語における文字列末尾のnull文字'\0'なども番兵の1つです。こうした細かいテクニックを積み重ねていくことで、ソースコードがよりシンプルな美しいものになり、ミスも少なくなるでしょう。

using System;
public class NotTwo
{
    public int maxStones(int width, int height)
    {
        int i, j;
        int[,] board = new int[1005, 1005];     //盤面の状態を格納。大きめに確保しておく
        int res = 0;
        for (i = 2; i < width + 2; i++)         //2つずらすことによって、例外処理を無くす
        {
            for (j = 2; j < height + 2; j++)    //番兵と呼ばれるテクニック
            {    
                if (board[i - 2, j] == 0 && board[i, j - 2] == 0)
                {
                    res++; board[i, j] = 1;
                    Console.Write("○");
                }
                else Console.Write("＋");
            }
            Console.WriteLine();
        }
        return res; 
    }
}

　これを利用して、縦10横10程度のサイズの結果を出力してみると、結果は以下のようになります。

○○＋＋○○＋＋○○
○○＋＋○○＋＋○○
＋＋○○＋＋○○＋＋
＋＋○○＋＋○○＋＋
○○＋＋○○＋＋○○
○○＋＋○○＋＋○○
＋＋○○＋＋○○＋＋
＋＋○○＋＋○○＋＋
○○＋＋○○＋＋○○
○○＋＋○○＋＋○○

　きれいな模様になりましたね。これは適当に左上から詰めた場合ですので最善であるという証明はまったくできていませんが、「これで良さそう！」と思えば、競技中はこれで○の数を数えて提出してしまっても構わないでしょう。マスの数は100万個しかなく、左上から詰めていく場合、プログラムを見れば明らかなように、実行時間はO（height*width）程度になるので（オーダーを極める思考法も参照ください）、問題なく終わることが容易に予測できます。石が置けるかどうかの判定は対象となる4つのマスのうち、上と左の2つだけを調べれば十分ですので、無視して問題ないレベルでしょう。

　さて、この出力を踏まえた上で、どう置けばよいかを考えてみましょう。上述の出力では、石は2*2の4つずつまとめて置かれていることが分かります。これがどうしてこうなるかを考えれば、石が置けるか置けないかというのは2つ離れたマスにしか関係なく、隣り合ったマスには影響されないからだということが分かります。となると、図を下のように塗りわけることができます。

　こうして塗り分けてみると、上下左右に2つ離れているマス以外は石が置けるかどうかに関与しないので、同じ色のマス以外はまったく関与しません。よって、図のようにこの同じ色のマスをくっつけると、隣り合ったマスに置けない場合の最大の置ける数となり、問題が非常に単純化されます。

　この4色の盤面における最大のマスを求めればよいのですが、こうなれば非常に簡単です。左上から順番に敷き詰めていけば、下の図のようになり最善であることは明らかだといえるでしょう。これにより、最初にあげたプログラムの表示例が最善な例の1つであったことも証明できます。

　そこまで分かれば簡単です。上のコードを少し変えて提出してしまってもよいのですが、せっかくですからビューティフルコードを目指しましょう。各色の盤面に置ける石の数は、前記理由から（マスの数+1）/2で求めることができます。それにより、4色の盤面それぞれに対し計算を行い、和を取るだけで、答えを求めることができます。プログラムは以下のようになります。

using System;
public class NotTwo
{
    public int maxStones(int width, int height)
    {
        int i, j, res = 0;
        for (i = 0; i < 2; i++)
        {
            for (j = 0; j < 2; j++)
            {
                res += (((width + i) / 2) * ((height + j) / 2) + 1) / 2;
            }
        }
        return res;
    }
}

　この時の計算量はO（1）であり、例えば縦横が10万程度に増えたとしても、int型をlong型に変えるだけで、一瞬で答えを求めることが可能です。もちろん、こういったソースコードが一発で書けるのが理想ですが、最初のようなプログラムを経由することも勉強になりますし、計算が十分間に合うのであれば、最初は無理せず確実なプログラムをかければ十分でしょう。

　ただし、こういった問題で重要なのは、「本当にそのプログラムで正しく動くのか」「本当にその予想は正しいのか」といったことです。とはいえ、数学のように堅苦しい証明を書け、というつもりはありませんし、直感的に「これで大丈夫なはず！」程度の確信が持てれば十分です。きちんと証明ができることも大切ですが、こういった感覚を身に着けていくことも非常に大切です。

　今回の問題も解き方は当然1つではなくさまざまな方法があります。プログラムを書く人によって、かなり書き方が変わってくるのではないかと思いますし、実際TopCoder本番中に提出されているプログラムにも、強烈に個性が見られるプログラムも数多く存在します。ぜひ、ほかの上位陣のソースコードもごらんいただければと思います。

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

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

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