ログを切り詰めてデータベースに保存する際の最大サイズを求めるPythonプログラム

数値のリスト logs と値 limit が与えられているとします。リストの各要素 logs[i] は i 番目のユーザーが生成したログのサイズを表し、limit はデータベースに保存できるログの合計サイズの上限を表します。ここで、logs 内のすべてのログをサイズ x 以下に切り詰めたとき、残ったログサイズの合計が limit 以下となるような最大の x を求める必要があります。なお、どのログも切り詰める必要がない場合は、単純に最大のログサイズを返します。

例として、入力が logs = [500, 200, 10000, 500, 4000]、limit = 3000 の場合を考えてみましょう。このときの出力は 900 になります。すべてのログを 900 で切り詰めると [500, 200, 900, 500, 900] となり、合計がちょうど 3000 になるためです。

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

この問題は二分探索（バイナリサーチ）を使うことで効率的に解けます。切り詰めサイズ x を大きくするほどログの合計は単調に増加するため、「条件を満たす最大の x」を範囲を半分ずつ絞り込みながら探せます。

具体的な手順は次のとおりです。

• lo := 0
• hi := 1 + logs の最大値
• lo + 1 < hi を満たす間、以下を繰り返す
  • mi := lo + (hi − lo) ÷ 2 の商（切り捨て）
  • sum(min(mi, log) for log in logs) <= limit であれば、lo := mi
  • そうでなければ、hi := mi
• 最後に lo を返す

計算量は O(n log(max(logs))) となり、ログの総当たり的な探索よりも大幅に高速です。

実装例

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

def solve(logs, limit):
    lo, hi = 0, max(logs) + 1
    while lo + 1 < hi:
        mi = lo + (hi - lo) // 2
        if sum(min(mi, log) for log in logs) <= limit:
            lo = mi
        else:
            hi = mi
    return lo

logs = [500, 200, 10000, 500, 4000]
limit = 3000
print(solve(logs, limit))

入力

[500, 200, 10000, 500, 4000], 3000

出力

900