Pythonで3つの街灯ですべての家を照らすための最小半径を求めるプログラム

1次元の直線上にある家の位置を表す数値リスト nums が与えられているとします。ここで、3つの街灯を直線上の任意の位置に設置でき、位置 x にある街灯は範囲 [x − r, x + r]（両端を含む）内のすべての家を照らせるものとします。このとき、すべての家を照らすために必要な最小の半径 r を求めます。

たとえば、入力が nums = [4, 5, 6, 7] の場合、出力は 0.5 になります。街灯を 4.5、5.5、6.5 の位置に配置すれば r = 0.5 となり、この3つの街灯ですべての4軒の家を照らすことができます。

解法のアプローチ

この問題は二分探索と貪欲法を組み合わせることで効率的に解くことができます。

• 単調性： 半径 r が大きくなるほど照らせる範囲も広がるため、「半径 r ですべての家を照らせる」という条件には単調性があります。つまり、ある r で可能なら、それより大きい r でも必ず可能です。この性質があるため、答えとなる r を二分探索で絞り込めます。

• 貪欲法による判定： 半径 r が固定されれば、3つの街灯で足りるかどうかは貪欲法で判定できます。まず左端の家をちょうどカバーできる位置（nums[0] + r）に最初の街灯を置きます。以降、まだ照らされていない家が現れたら、その家をちょうどカバーできる位置に新しい街灯を置きます。最終的に必要な街灯の本数が3本以下であれば、その r は有効です。

• 収束処理： 探索対象が整数ではなく実数のため、二分探索を固定回数（今回は20回）繰り返して、十分な精度まで答えを収束させます。

アルゴリズムの手順

まず、判定用の関数 valid() を定義します。引数として半径 r を受け取ります。

• last_location := nums[0] + r（最初の街灯の位置）

• count := 1（使用した街灯の本数）

• i を 0 から nums のサイズまで繰り返す：

  • val := nums[i]

  • val - last_location > r の場合（現在の街灯では届かない家がある場合）：

    • count := count + 1

    • last_location := val + r（新しい街灯を置く）

• count <= 3 なら true を返し、そうでなければ false を返す

続いて、メイン処理では以下の手順を実行します。

• リスト nums をソートする

• left := 0、right := nums の最後の要素、res := 無限大、itr := 0 で初期化する

• left <= right かつ itr < 20 の間、次を繰り返す：

  • mid := left + (right - left) / 2

  • valid(mid) が true の場合：

    • res := min(res, mid)

    • right := mid（より小さい r を探す）

  • それ以外の場合：

    • left := mid（より大きい r を探す）

    • itr := itr + 1

• res を返す

実装例

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

class Solution:
   def solve(self, nums):
      def valid(r):
         last_location = nums[0] + r
         count = 1
         for i in range(len(nums)):
            val = nums[i]
            if val - last_location > r:
               count += 1
               last_location = val + r
         return count <= 3
      nums.sort()
      left = 0
      right = nums[-1]
      res = float("inf")
      itr = 0
      while left <= right and itr < 20:
         mid = left + (right - left) / 2
         if valid(mid):
            res = min(res, mid)
            right = mid
         else:
            left = mid
         itr += 1
      return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))

入力

[4,5,6,7]

出力

0.5