PythonでK時間以内にすべての石を取り除くための最小の除去率を求めるプログラム

数値のリスト piles と値 k が与えられているとします。piles[i] は i 番目の山にある石の数を表します。私たちは毎時間、任意の山を1つ選び、そこから r 個の石を取り除くことができます。ただし、選んだ山に r 個未満の石しか残っていない場合でも、その山を空にするには1時間かかるものとします。このとき、すべての石を k 時間以内に取り除けるような r の最小値を求めるのがこの問題です。

例として、入力が piles = [3, 6, 4]、k = 5 の場合を考えてみましょう。このとき出力は 3 になります。なぜなら、r = 3(毎時3個ずつ取り除く)と設定すれば、2番目の山(6個)を2時間で、3番目の山(4個)を2時間で、そして1番目の山(3個)を1時間で片付けられ、合計5時間ですべての石を処理できるからです。

解き方：二分探索によるアプローチ

この問題は「二分探索」を使うことで効率的に解くことができます。r の候補範囲は 1 から piles の最大値までなので、その中から条件を満たす最小値を絞り込んでいきます。手順は以下の通りです。

• 探索範囲の下限 l を 1、上限 h を piles の最大値に設定し、答えとなる r の初期値も h とします。
• 関数 turns(r) を定義します。これは、各山 b について ceil(b / r)(b を r で割った値の切り上げ)を求め、その合計を返すものです。つまり、速度 r で作業した場合に必要な総時間を表します。
• メインの処理では、l < h の間、以下を繰り返します。
  • mid := (l + h) / 2 の切り捨て値とします。
  • turns(mid) > k であれば、mid の速度では k 時間以内に終わらないため、l := mid + 1 として探索範囲を上げます。
  • そうでなければ、mid の速度で十分なので、h := mid とし、r := min(r, mid) で答えを更新します。
• ループが終了したら r を返します。

このアルゴリズムの計算量は O(n log m) です(n は山の数、m は最大の山のサイズ)。各判定で全山を走査するため線形時間がかかりますが、二分探索により試行回数が対数オーダーに抑えられるため、大きな入力に対しても高速に動作します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

from math import ceil
def solve(piles, k):
    l = 1
    h = max(piles)
    r = h

    def turns(r):
        return sum(ceil(b / r) for b in piles)
    while l < h:
        mid = (l + h) // 2
        if turns(mid) > k:
            l = mid + 1
        else:
            h = mid
            r = min(r, mid)
    return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))

入力

[3, 6, 4], 5

出力

3