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

典型的なアルゴリズムをたくさん知っている人間が最強か――？　いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。

[高橋直大，ITmedia]

解法

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

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

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

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

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

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

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

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

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

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

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

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

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

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

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

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

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

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

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

*** 一部省略されたコンテンツがあります。PC版でご覧ください。 ***

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

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

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

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

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

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