「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」：最強最速アルゴリズマー養成講座（3/3 ページ）

解法

　まずはフラクタルの扱い方に関してです。マスの総数は最大4億個近くになってしまいますので、これを効率のよい保持の仕方にしましょう。

　下の図に注目してください。このフラクタルは、縦と横に関して対称性があるので、実は2次元の配列としてデータを持たずとも、1つの配列を使うだけで、縦と横の両方について、そのマスに色が塗られているかを判別できます。図を見れば一目瞭然（りょうぜん）ですが、座標（x,y）のマスが塗られているかを判別するときはこの1列だけを考え、x番目とy番目にともに色が塗られていれば、座標（x,y）のマスは塗られている、と判断することができます。

　この配列に関してですが、作り方は非常に簡単で、今回の問題のフラクタルを2次元から1次元に縮小しただけです。よって、以下のようなソースで簡単に再現することが可能です。

    public string getstring(int T) {
        //最初は"X"の1文字
        if (T==0) return "X";
        //1つ前の1辺を生成する
        string c = getstring(T - 1);
        //1つ前の1辺から、新しい1辺を生成する
        return c + new string(' ', c.Length) + c;
    }

　ここで、あることに気がつければ、答えは非常に簡単に求めることができます。それは、同じ列、行に関して、まったく色が塗られていない、もしくは先ほど求めた配列とまったく同じ色の塗られ方をしている、の2通りしか存在しない、ということです。

　これを踏まえた上で、以下のような検索パターンについて考えてみます。

X.X.X
.....
X...X
.....
X.X.X

　前記のことを踏まえれば、上のパターンは、いくらフラクタルを生成するtime数を増やしたとしても、絶対に出現しないことが容易に分かります。なぜなら、1列目の色の塗られ方（X.X.X）と、3列目の色の塗られ方（X...X）が異なっているからです。

　色の塗られている列の塗られ方は1つしかないはずであり、これは先ほどの結果と矛盾するので、このフラクタルにこういったパターンが出てこないことが分かります。

　ここで、これをさらに発展させます。下のようなパターンを考えてみましょう。

X.X...X.X
.........
X.X...X.X
.........
.........

　このパターンは、前記の条件に矛盾しないので、存在する可能性のあるパターンといえます。色が塗られている行は必ずX.X...X.Xとなっていますし、色が塗られている列は必ずX.X..という並びになっています。ということは、先ほど作った配列を利用して、配列中にX.X...X.Xが出てくる回数と、X.X..が出てくる回数が、それぞれ、縦の列が条件を満たす範囲の数、横の行が条件を満たす範囲の数、となります。

　よって、これらの数を掛け合わせることで、下図のようになり、求めるパターンの出現数を簡単に求めることができます。

　ここまでが、わたしが本番中に辿り着いた答えです。ただし、これでは不十分なところが残ってしまいます。それは、入力されたパターンで、まったく色の塗られているところが存在しない場合です。例を考えてみましょう。time=1のフラクタルは以下のようになります。

X.X
...
X.X

　ここで、色の塗られていない色1マスをパターンとして検索すると、前記アルゴリズムでは、中心の1マスしか見つけられません。ですが、実際は色の塗られていないマスは明らかに5マス存在します。色がまったく塗られていないパターンの場合、こうして間に入り込むことが可能となるわけです。このため、色がまったく塗られていないパターンに対しては、特別な処理をする必要があります。

　とはいっても先ほどとたいして変わるわけではありません。ここで気付くべきなことは、そのパターンが十分に入り込めるだけの行、列の空間がある場合、そこから1行、1列ずらしたパターンはすべて当てはまる、ということだけです。これに気づけば、先ほどの式を少し変えるだけで簡単に式が立てられます。

　縦の列が条件を満たす範囲の1つに対し、1辺の長さからそのパターンの横の長さを引いただけの数のパターンが検出できますし、同様のことを横方向に行えます。ここから、重複する部分を引けば良いですが、これは縦横の条件を満たす範囲の数の積であっさりと求めることができます。

　以上を踏まえた上で、いままでのものをまとめたソースコードは、前記getstring関数を使うものとして、以下のようになります。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class CantorDust {
    public string getstring(int T) {
        if (T==0) return "X";
        string c = getstring(T - 1);
        return c + new string(' ', c.Length) + c;
    }
    public int occurrencesNumber(string[] pattern, int time)
    {
        int M = pattern.Length, N = pattern[0].Length;  //縦、横の長さ
        bool[] a = new bool[M], b = new bool[N];    //各列・行にXを含むか否かのflag
        string C = getstring(time);    //上記getstring関数からフラクタルの1列を生成する
        int L = C.Length;   //フラクタルの1辺の長さ
        int x, y, k;
        int p = 0, q = 0;   //pが横のパターンの一致数、qが縦のパターンの一致数
        bool flag = false;
        //各列・行に'X'を含んでいるかを調べる
        for (x = 0; x < M; ++x) for (y = 0; y < N; ++y) if (pattern[x][y] == 'X') a[x] = b[y] = flag = true;
        //矛盾を含んでいたら存在しないので、0を返す
        for (x = 0; x < M; ++x) for (y = 0; y < N; ++y) if ((pattern[x][y] == 'X') != (a[x] && b[y])) return 0;
        //横について一致数を調べる　C#ならIndexOf、C++ならfind等を使っても可
        for (k = 0; k + M <= L; ++k)
        {
            for (x = 0; x < M; ++x) if ((C[k + x] == 'X') != a[x]) break;
            if (x == M) ++p;
        }
        //縦についても同様に
        for (k = 0; k + N <= L; ++k)
        {
            for (y = 0; y < N; ++y) if ((C[k + y] == 'X') != b[y]) break;
            if (y == N) ++q;
        }
        if (flag) return (p * q);   //'X'を含む場合
        else return (p * (L - N + 1) + (L - M + 1) * q - p * q);    //'X'を含まない場合
    }
}

　今回の解説ですが、問題の難度にふさわしくかなり分かりにくいものになってしまっていると思います。一度読んだだけで理解できる方はよいのですが、そうでなければ、図を紙に描きながら何度も考えながら読んでいただければ良いな、と考えています。

　今回のアルゴリズムですが、見て分かるとおり、特別なアルゴリズムは一切使用しませんでした。このような方法が通じるのはこのフラクタルだけですし、ほかの問題ではまた別の方法で臨む必要がありますが、既存の有名なアルゴリズムを使わなくても、ただ気づいた点をまとめ、効率よく計算していくだけで、答えを求めることは十分に可能であることを示せたかと思います。また、まったく同じアルゴリズムはまず使えないでしょうが、少し違ったものにも自力で対応できるようになるのではないかと思います。

　今回は方法を実質1つしか紹介していませんが、ほかの方法もまだまだ存在します。今回紹介した方法だけに捕らわれずに、いろいろな方法で挑戦してみるのも面白いかと思いますし、ぜひ挑戦してほしいです。「こんな実装もあるよ」といった、記事に関するご意見もお待ちしています。それでは次回もお楽しみに！