【Python】k個の監視ステーションで特定のポイントを監視できるか判定するプログラム

半径r以内の周辺環境を監視できるセンサーモジュールを想定してみましょう。このモジュールの監視円の円周上にある格子点の中には、監視が必要な対象がいくつか存在します。そこで、それらの特定のポイントのみを監視できるように、低消費電力のモジュールをk個配置することを考えます。半径の二乗(j)と低消費電力モジュールの数(k)が与えられたとき、すべてのポイントを正しく監視できるかどうかを判定するのが本記事の目的です。監視が可能であればtrueを、不可能であればfalseを返します。

たとえば、入力が半径の二乗(j) = 4、監視ポイント数(k) = 3だった場合、出力はFalseになります。

j = 4のとき、監視円の円周上には(0, 2)、(0, -2)、(2, 0)、(-2, 0)という4つのポイントが存在します。そのため、監視ステーションを3つ用意しただけでは、すべてのポイントを完全にカバーすることができません。

解決のためのアプローチ

この問題は、次の手順で解決できます。

• square_set := 44721までの値の二乗を格納した集合を作成する
• i := 0、res := 0 で初期化する
• i < √j の間、以下を繰り返す
  • (j − i²) がsquare_setに存在する場合は、res := res + 1
  • i := i + 1
• res := res × 4
• k ≥ res であればTrueを返す
• そうでなければFalseを返す

なぜこの方法が機能するのか

このアルゴリズムは、円 x² + y² = j の円周上に存在する格子点の個数を数えています。x座標を0から順に確認し、j − x² が平方数（square_setに存在）であれば、対応する点が円周上に存在することを意味します。円は原点を中心として対称な図形なので、見つかった1つの点は回転によって4つの象限それぞれに対応し、最後にresを4倍することで円周上の格子点の総数が求まります。この総数が用意したステーション数k以下であれば、全ポイントの監視が可能だと判定できます。

実装例

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

square_set = set([z ** 2 for z in range(44722)])
def solve(j, k):
    i = 0
    res = 0
    while i < (j ** 0.5):
        if j - i ** 2 in square_set:
            res += 1
        i += 1    
    res *= 4
    if k >= res:
        return True
    else:
        return False

print(solve(4, 3))

入力

4, 3

出力

False