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

[高橋直大，ITmedia]

今回の問題

　では今回の問題です。今回は、Member BetaのDiv1 Mediumより出題です。

Cantor dust is a 2-dimensional fractal constructed in the following way. Initially the fractal is a black square. At each iteration, each square of the fractal is divided into a 3x3 subgrid of equal subsquares. Any black subsquares which belong to the middle row or to the middle column of a subgrid （or to both of them） are painted white.

You are given a String[] pattern which represents a rectangular pattern of black and white squares （represented by 'X' and '.' characters, respectively）. Return the number of occurrences of this pattern in Cantor dust at iteration time. Overlapping occurrences are allowed.

Constraints

- time will be between 1 and 9, inclusive.

- pattern will contain between 1 and min（50, 3^time） elements, inclusive.

- Each element of pattern will contain between 1 and min（50, 3^time） characters, inclusive.

- All elements of pattern will contain the same number of characters.

- Each character in each element of pattern will be '.' or 'X'.

　これをいつも通り適当に和訳すると、次のルールに従って2次元フラクタルを生成し、指定されたパターンが何個出現するかを求める問題となります。

　以下の図のように、最初は1*1のマスがあります（色が塗られているマスはXで表しています）。これを縦横に3分割し、分割された色の塗られたマスの中央のラインを縦・横ともに白く塗りつぶします。この操作を引数timeによって指定された回数繰り返し、フラクタルを生成します。

　このとき、このような文字列配列によって、探すパターンを指定します。

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

　こうして指定されたパターンが、このフラクタル中に幾つ含まれているかを求めるのが今回の問題です。なお、問題のサイズは、1≦time≦9、指定されるパターンのサイズは最大50*50までとなっています。

　今回も問題に取り組みすいように、問題挑戦用のソースコードを用意しました。問題側で設定されたサンプルデータが前半に5つと、本当に正しいかどうかを検証するための凶悪なデータの後半5つを自動でチェック可能になっていますので、気軽に問題への挑戦が可能となっています。C++、C#、Javaの3種類を用意しましたので、好きな言語で挑戦してみてください。

ソースコードのダウンロードはこちらから

ヒント

　今回扱うフラクタルは、非常にサイズが大きくなっていきます。これをどう扱うかが最初の問題となります。問題文中では3分割と書かれていますが、以下の図のように、timeが1進んだ状態を大きさが縦横ともに3倍になったものと考えれば、下図（右）のように、元の構造が隅に4つ、中央の5つは同じ大きさで、すべて白く塗られているもの、とみることができます。

　これを利用すれば、比較的容易にこのフラクタルを作成することは可能でしょう。しかし、このフラクタルは、最大で一辺が3^9=19683となり、2次元配列などに格納することは不可能です。ここをどう扱うかが第一のポイントになるでしょう。