Pythonでボールの入った袋のペナルティを最小化するプログラム（二分探索による解法）

nums という配列があり、i 番目の要素は nums[i] 個のボールが入った袋を表しているとします。さらに、mx という別の値も与えられます。この mx は、以下の操作を実行できる最大回数を意味します。

• 任意のボールの入った袋を1つ選び、少なくとも1個ずつのボールが入った2つの新しい袋に分割する。
• ここで「ペナルティ」とは、すべての袋の中で最も多くのボールが入っている袋のボール数を指します。

私たちの目的は、操作を最大 mx 回まで行った後のペナルティを最小化すること、すなわち実現可能な最小のペナルティを求めることです。

例えば、入力が nums = [4,8,16,4]、mx = 4 の場合、出力は 4 になります。これは次のような手順で操作できるためです。

1. 初期状態：[4,8,16,4]
2. 16個のボールが入った袋を、8個ずつの2つの袋に分割 → [4,8,8,8,4]
3. 8個の袋をそれぞれ4個ずつに分割 → [4,4,4,8,8,4] → [4,4,4,4,4,8,4]
4. 最終的に [4,4,4,4,4,4,4,4]

こうしてすべての袋が4個になり、最小ペナルティは4となります。

解法のアプローチ

この問題は二分探索を使って効率的に解けます。基本的な発想は、「ペナルティを target 以下にするために必要な分割回数が mx 回以内に収まるか？」という判定関数を作り、target の候補値を二分探索で絞り込んでいくというものです。

helper() 関数の手順

• 引数として target と mx を受け取る関数 helper() を定義します。
• target が 0 の場合は mx + 1 を返します（判定を必ず失敗させるため）。
• count := 0 と初期化します。
• nums の各要素 num に対して、count := count + (num - 1) // target を加算していきます。これは各袋を target 以下にするために必要な分割回数です。
• 最後に count <= mx を返します。

メイン処理の手順

• left := max(sum(nums) // (len(nums) + mx), 1) —— 理論上の下限値
• right := max(nums) —— 袋の中の最大ボール数
• left < right の間、以下を繰り返します。
  • mid := (left + right) // 2
  • helper(mid, mx) が真であれば right := mid
  • そうでなければ left := mid + 1
• 最後に left を返します。

実装例

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

def helper(target, mx):
    if target == 0:
        return mx + 1
    count = 0
    for num in nums:
        count += (num - 1) // target
    return count <= mx

def solve(nums, mx):
    left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
    while left < right:
        mid = (left + right) // 2
        if helper(mid, mx):
            right = mid
        else:
            left = mid + 1
    return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

入力

[4,8,16,4], 4

出力

4