Pythonで爆弾に触れずに長方形領域を貫通する連続経路を判定するプログラム

問題の概要

ここでは、配列 mat が与えられたときの問題を考えます。各要素は [p, q, r] という形式で表され、p と q は幾何学的な座標(x座標・y座標)、r は半径の値です。配列の各要素は、幅 w の長方形領域内にある爆弾の位置を示しています。

この長方形は上下方向に無限に伸びており、左右は x = 0 と x = w という2本の直線で囲まれています。爆弾が持つ r の値は安全半径を意味し、爆弾の中心からこの半径以内に近づくと爆発してしまいます。

求められているのは、すべての爆弾の下側からスタートし、すべての爆弾の上側でゴールする連続した経路を、どの爆弾にも触れずに引けるかどうかの判定です。経路が引けるなら True を、引けないなら False を出力します。

入力例

たとえば、入力が次のようだったとします。

このとき w = 4 であれば、出力は False になります。爆弾同士の安全円が互いにつながり、左端から右端まで「壁」を形成してしまうためです。

解き方のステップ

この問題を解くには、次の手順に従います。

• 関数 insec() を定義する。2つの爆弾 p, q を受け取り、それぞれの安全円が交差(接触)しているかどうかを判定します。
  • x1 := p[0]、y1 := p[1]、x2 := q[0]、y2 := q[1](それぞれの中心座標)
  • r1 := p[2]、r2 := q[2](それぞれの半径)
  • d := (x1 − x2)² + (y1 − y2)²(中心間距離の2乗)
  • dec := (r1 + r2)²(半径の和の2乗)
  • d ≤ dec なら True(交差している)、そうでなければ False を返す
• 爆弾のリストを x 座標の値に基づいてソートします。
• temp := 空の新しいリストを用意します。
• もし最初の爆弾が左端(x = 0)に触れていなければ(mat[0][0] − mat[0][2] > 0)、True を返します。
• mat 内の各爆弾 (p, q, r) について、以下を繰り返します。
  • min_wid := p − r、max_wid := p + r とします。
  • temp が空の場合は、リスト [p + r, p, q, r, p − r, p + r] を temp の末尾に追加します。
  • そうでない場合は、次のように処理します。
    • mx := bisect_left(temp, [p − r, −p, q, r, 0, 0]) − 1 と 0 のうち大きい方(ソート順を保ったまま挿入できる位置)
    • in_list := [p + r, p, q, r, p − r, p + r] という新しいリストを作成します。
    • i を mx から temp のサイズまで動かしながら、insec(temp[i], in_list) が True であれば、max_wid を max(max_wid, temp[i][-1]) で、min_wid を min(min_wid, temp[i][-2]) で更新します。
    • in_list の後ろから2番目の要素に min_wid を、最後の要素に max_wid を代入します。
    • in_list をソート順を維持したまま temp に挿入します。
  • もし min_wid ≤ 0 かつ max_wid ≥ w であれば、False を返します(爆弾の連なりが左右の境界をつなぐ壁になっていることを意味します)。
• 最後に True を返します。

アルゴリズムのポイント

このアプローチの核心は、「爆弾の安全円同士が交差して鎖状につながり、その鎖が左端(x = 0)と右端(x = w)の両方に達していれば、上下を貫く経路は存在しない」という事実です。各爆弾について、交差する既存のグループと統合しながら到達可能な最小・最大の x 範囲(min_wid / max_wid)を追跡することで、壁の完成を効率的に検出できます。

実装例

理解を深めるために、以下の実装を見てみましょう。

from bisect import bisect_left, insort
def solve(mat, w):
    mat.sort(key=lambda i: i[0] - i[2])
    temp = []
    if mat[0][0] - mat[0][2] > 0:
        return True
    for p, q, r in mat:
        min_wid, max_wid = p - r, p + r
        if len(temp) == 0:
            temp.append([p + r, p, q, r, p - r, p + r])
        else:
            mx = max(bisect_left(temp, [p - r, -p, q, r, 0, 0]) - 1, 0)

            in_list = [p + r, p, q, r, p - r, p + r]
            for i in range(mx, len(temp)):
                if insec(temp[i], in_list):
                    max_wid = max(max_wid, temp[i][-1])
                    min_wid = min(min_wid, temp[i][-2])
            in_list[-2] = min_wid
            in_list[-1] = max_wid
            insort(temp, in_list)
        if min_wid <= 0 and max_wid >= w:
            return False
    return True

def insec(p, q):
    x1, y1, x2, y2 = p[1], p[2], q[1], q[2]
    r1, r2 = p[3], q[3]
    d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
    dec = (r1 + r2) * (r1 + r2)
    return d <= dec

print(solve([[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4))

入力

[[0, 1, 2],[3, 2, 1], [2, 1, 1]], 4

出力

False