Pythonでバケット内のボール間の最小力を最大化するアルゴリズムの実装方法

複数のバケットと x 個のボールが与えられたとします。ボールをバケットに入れると、ボール同士の間に特別な力が働き、「2つのボール間の最小力」を最大化するような配置を見つける必要があります。位置 p と q にある2つのボール間の力は |p − q| で表されます。入力として、バケットの位置を格納した配列とボールの個数 x が与えられ、その中で実現できる最小力を求めます。

例えば、入力が pos = [2, 4, 6, 8, 10, 12]、x = 3 の場合、出力は 4 になります。

この場合、3つのボールをそれぞれ位置 4、8、12 に置くことで、ボール間の力は 4 になります。これ以上この値を大きくすることはできません。

解決のためのアプローチ：二分探索

この問題は「答えに対する二分探索」と貪欲法（グリーディ法）を組み合わせることで効率的に解けます。ある距離 d が実現可能かどうかを判定する関数を作り、d の値を二分探索で絞り込んでいくのがポイントです。具体的には、以下の手順に従います。

• ball_count() 関数を定義する。引数 d を受け取り、隣接するボール間の距離が d 以上になるように配置したとき、何個のボールを置けるかを返します。
  • ans := 1、curr := pos[0] と初期化する
  • i を 1 から n までループし、pos[i] − curr ≥ d であれば ans を 1 増やし、curr := pos[i] と更新する
  • ans を返す
• n := pos のサイズとする
• リスト pos をソートする
• left := 0、right := pos[-1] − pos[0] と初期化する
• left < right の間、以下を繰り返す
  • mid := right − floor((right − left) / 2)
  • ball_count(mid) ≥ x であれば left := mid、そうでなければ right := mid − 1
• left を返す

ball_count() は左端から順にボールを置いていく貪欲な判定であり、指定した距離 d 以上の間隔で最大何個配置できるかを O(n) で求められます。これにより、全体の計算量は O(n log D)（D は最大距離）に抑えられます。

実装例

以下の Python コードを見ると、処理の流れがより理解しやすくなります。

def solve(pos, x):
    n = len(pos)
    pos.sort()

    def ball_count(d):
        ans, curr = 1, pos[0]
        for i in range(1, n):
            if pos[i] - curr >= d:
                ans += 1
                curr = pos[i]
        return ans

    left, right = 0, pos[-1] - pos[0]
    while left < right:
        mid = right - (right - left) // 2
        if ball_count(mid) >= x:
            left = mid
        else:
            right = mid - 1
    return left

print(solve([2, 4, 6, 8, 10, 12], 3))

入力

[2, 4, 6, 8, 10, 12], 3

出力

4

このように、二分探索と貪欲法を組み合わせることで、ボール間の最小力を最大化する最適な配置を効率よく求めることができます。