あなたの論理的思考とコーディング力は3倍高められる：最強最速アルゴリズマー養成講座（2/2 ページ）

[高橋直大，ITmedia]

実際の問題はこんな感じ

　本稿で紹介している問題は、TopCoderのSRMで出題されたものを引用する形で紹介させていただきます。ここでは、あるSRMでのDiv1Easy（かつDiv2Meidum）の問題を示します。

問題文

Circles Country is a country that contains several circular-shaped districts. Some districts may be situated inside other districts, but their borders do not intersect or touch. Qatam is a resident of Circles Country. When he travels between two locations, he always tries to cross the fewest number of district borders as possible because crossing borders is usually a laborious task.

Imagine Circles Country as an infinite plane. You are given int[]s X, Y and R, where (X[i], Y[i]) are the coordinates of the i-th district's center and R[i] is its radius. Qatam is currently at point (x1,y1) and he needs to get to point (x2,y2). Neither of these points lies on a district border. Return the minimal number of district borders he must cross to get to his destination.

　はい。いきなり英語で面倒くさいですね。問題文を見ただけでやる気をそがれる方も多いでしょう。一言一句正確に日本語訳していては時間のロスですので、大意をつかむのがコツとなります。この問題文を著者なりに意訳すると以下のようになります（強調は著者）。

始点、終点の座標と、途中にある円の中心座標、半径が与えられる。始点から終点に移動するとき、円周の線をまたがなければならない回数の最小回数を求めよ。ただし、円同士の円周・始点・終点は接触しないものとする。

実装方針の検討

　この問題は、幾何・グラフの問題です。一見難しく見えるかもしれませんが、実は中学1、2年程度の知識があれば十分見通しを立てることができます。直感的に簡単な実装が思いつく人も多いと思いますが、まず愚直な実装を考えてみましょう。

　複数の円に対して、「円が必ず交差しない」ということは、ある円は、円の内側か外側にいるかのどちらかしかあり得ないということになります。このため、ある円に対し、その内側にいる円を子として持つ、木構造のデータ構造として管理することができます。ここで、さらに出発点・目的地の2つの点も半径0の円として管理すると、より見通しがよくなります。

　文章だけだと分かりにくいかもしれませんので、図で考えてみましょう。図1のような円の集合が与えられたとき、木構造でまとめると、図2のようになります。木構造というと難しく思えるかもしれませんが、実際には実装に使うわけでもありませんので、図を見てイメージができればそれで十分です。

図1を木構造でまとめたもの

　こうして木構造が完成したら、ノード間の移動がそのまま境界をまたぐ数となるため、後は深さ優先探索などで2点間の距離を求めれば、境界をまたぐ最小数を求めることができるのです（図3）。

図3

美しい実装を求めて

　方針のめどは立ちましたが、これを素直に実装しようとするとソースコードが長くなります。ここでは、「円の境界をまたぐ」という部分に着目し、より美しい実装がないか考えてみます。

　円の境界をまたぐ、という行為は、円の中から外に出る、もしくは、円の外から中に入る、のいずれかしかありません。ということは、各々の円に対して、

• 出発点と目的地が両方とも円の内部であれば、その内部の中で移動すれば、境界をまたぐ必要はない
• 同様に、出発点と目的地が両方とも円の外部であれば、その円のないところを移動すればよい
• 逆に、出発点と目的地がそれぞれ、片方が円の外部、片方が円の内部であれば、1回は円をまたぐ必要がある

ということになり、またぐ必要のある円の数を数えるだけで、答えを求めることができます。

　ここで、同じ円の外に出てまた内側に入る、もしくはその逆が必要なケースを考える方がおられるかもしれません。しかし、先ほどの木構造の図を見ると、同じ場所を上下に行ったり来たりしてしまうだけでまったく意味がないことが分かります。

　これを実際に実装してみると以下のようになります。

using System;
public class CirclesCountry {
    public int leastBorders(int[] X, int[] Y, int[] R, int x1, int y1, int x2, int y2)
    {
        int count = 0;
        for (int i = 0; i < X.Length; i++)
        {
            if (checkInside(X[i], Y[i], x1, y1, R[i]) ^ checkInside(X[i], Y[i], x2, y2, R[i])) count++;
        }
        return count;
    }
    bool checkInside(int x1, int y1, int x2, int y2, int r)
    {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= r*r;
    }
} 

　比較的すっきりとまとめることができました。ちなみに著者の場合、このコードができあがるまで、実装の検討で5分、コーディングが3分といったところです。英語での設問にたじろいでしまうかもしれませんが、実装の方針さえしっかりと立ってしまえば、容易な問題といえるのではないでしょうか。「こんな実装もある」などのご意見もお待ちしています。次回もお楽しみに。

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

Microsoftが毎年開催している「Imagine Cup 2008」のアルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。現在、慶應義塾大学環境情報学部2年。口癖は「みょんみょん」。