四角い頭は丸くなるのか

未知の問題を解くとき、自分を許せる場合と許せない場合がある。許せる場合、それは解法に必要な理論をまったく知らなかったとき。見たこともない数論、アルゴリズム、データ構造などが絡んで、既存の知識を総動員してもこれはたどりつけないと感じたとき。一方で許せない場合、それは解法に必要な武器は全て持ち合わせていたにも関わらず、問題に結び付けられなかったとき。山の手線内で「四角い頭を丸くする」という日能研のキャッチコピーをよく目にしたのを覚えているが、これを当てはめるなら、私の頭はがちがちに四角い。それは、パズルやオンラインジャッジの問題に取り組んでいて、解法に必要な武器は持ってるのに解けないケースが多すぎるからだ。なので、生まれてこのかた自分の脳に瞬発性があると思えたことは一度もない。数学ガールの第二巻「フェルマーの最終定理」でもテトラちゃんが似たような悩みを語っているので、詳しくは第二巻のページ 204 と 255 を参照あれ。

話しの具体性を出すため、例を挙げる。TopCoder の SRM269 の SecurityBunker という問題があり、ここでも自らの脳の反応の悪さを垣間見ることになった。問題は以下の通り。マップに爆弾（*）とシークレットオブジェクト（?）の二種類が配置されている。どの爆弾に着火してもすべてのシークレットオブジェクトに火が届くような火力のうち、最小の火力 D（答えは double 型）を算出してくれ、というもの。ボンバーマンのように他の爆弾の爆発による誘爆も許される。最小という言葉を見て最初に頭に思い浮かんだのは breath first search だったが、答えの火力が double 型だったので、これはおそらく上手くないだろうと判断。SRM187 の DNAMultiMatcher で tomek さんのうまい binary search を思い出して、この問題でも使えるかと疑ってみる。が、爆弾の爆発の連鎖をどう表すのかが思い浮かばずに脳がここで停止する。次の一手がどうしても出ず、ギブアップ。落胆しつつ、他のコーダーのアプローチを見ると、爆発の連鎖に union find を使っている・・・！Kruskal で使っていたはずなのに、状況が変わるともう使えない。かたい頭だ。こういう局面でキーポイントに気づく人と気付かない人の違いはなんなのか。

Andy Hunt 氏の「Pragmatic Thinking and Learning」の第二章に "Experts work from intuition, not from reason." という一文がある。達人コーダーはこの「勘」が凄い。考える前にもう何かが湧いてきてるのだろう。話しは変わるが、自分もテニスやっていてノッてたときはこの勘が冴えていた。これをダウンザラインに打ち込めばネットに出てボレーで決められるとか、このポイントではリターンをスライスで返せば相手のリズムを崩せるとか、理屈じゃない何かが見えていた時期があった。さらに話しが変わるが、すぎやまこういち先生がドラゴンクエストの序曲を作曲なさったとき、依頼をうけて帰りの車に乗り込んでから5分で思い浮かんだとか。曰く「ただの5分ではなくて、僕がこれまで生きてきた人生プラス5分」だそうだ。パンチラインは、経験から繰り出される直感は最強、ということ。問題が解けないのは、どうも私の頭が四角いとかいう言い訳じみたもののせいではなく、経験が圧倒的に不足しているからのようだ。経験が頭を丸くする。中には経験抜きで直感が冴えまくる人もいるだろうが、少なくとも私はその部類ではない。ロジカルシンキング以上に利くのは、経験に裏打ちされた直感ではないかと思うわけである。ただ厄介なのは、この直感というもの、狙って会得できるようなシロモノではなさそうなのだ。なんというか、努力と経験の末に生み出される副作用のような気がしている。脳科学や人工知能の観点からこれをどう説明できるのか、非常に興味があります。

以下、自分で書いた SRM269 の SecurityBunker の解答

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define FOR(i,s,e) for (int i = int(s); i != int(e); ++i)
template<typename T> inline int size(const T& c) { return c.size(); }

int p[200];vector <pair<int, int> > b, so;

int find(int x) { return p[x] == -1 ? x : (p[x] = find(p[x])); }

void joint(int x, int y) { x = find(x); y = find(y); if (x != y) p[x] = y; }

/*
 * This function returns true if all secret objects can be destroyed with
 * a given bomb range.
 */
bool ok(double cur) {
    // initialize each bomb's representative
    memset(p, -1, sizeof p);
    // if two bombs are within the range, merge them into one set
    FOR(i,0,size(b)) FOR(j,0,size(b))
        if (hypot(b[i].first - b[j].first,
                  b[i].second - b[j].second) < cur)
            joint(i, j);
    // if the representative in a disjoint set destroys all secret objects
    // so do all bombs in the set
    FOR(k,0,size(b)) if (p[k] == -1) {
        FOR(i,0,size(so)) {
            bool good = false;
            FOR(j,0,size(b)) {
                if (find(j) == k &&
                    hypot(b[j].first - so[i].first,
                          b[j].second - so[i].second) < cur) {
                    good = true;
                    break;
                }
            }
            if (!good) return false;
        }
    }
    return true;
}

class SecurityBunker {
public:
    double chooseBomb(vector <string> field) {
        FOR(i,0,size(field)) FOR(j,0,size(field[0])) {
            if (field[i][j] == '*') b.push_back(make_pair(i, j));
            if (field[i][j] == '?') so.push_back(make_pair(i, j));
        }
        // binary search on range D
        double lb = 0, ub = 200;
        while (ub - lb > 1e-9) {
            double cur = (ub + lb) / 2;
            // if all security objects can be destroyed with this range
            // look for a shorter range
            if (ok(cur)) ub = cur;
            // otherwise look for a longer range
            else lb = cur;
        }
        return lb;
    }
}