概要

各届け先に配送する荷物の個数と、一日あたりの配送能力が与えられる。配送能力を最大 \(M\) まで増やせるとき、全ての荷物を配送するのに必要な最小日数を求める問題。

考察

各届け先 \(i\) への配送日数は \(\lceil A_i / (K + x) \rceil\) であり、全体の日数はこれを全ての \(i\) について足し合わせたものです。
ここで、\(x\) を増やすと各項の値は減るか変わらないため、関数

\[ f(x) = \sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil \]

は広義単調減少になります。しかし、単調減少だからといって必ずしも二分探索で最小値を求められるわけではありません（なぜなら関数が離散的かつ階段状に変化するため）。

素朴な方法として、\(x = 0\) から \(x = M\) まで全て試す方法がありますが、\(M\) が最大 \(10^9\) なので現実的ではありません（TLE）。
このような「ある関数の最小値を求める」問題で、関数が凸っぽいか単調な場合、三分探索が有効です。

この問題では、関数 \(f(x)\) は厳密には凸ではありませんが、大域的には下に凸に近い形をしているため、三分探索によって最小値に近い箇所を効率的に求められます。

アルゴリズム

1. 関数 \(f(x) = \sum_{i=1}^{N} \left\lceil \frac{A_i}{K + x} \right\rceil\) を定義します。
2. この関数の最小値を、区間 \([0, M]\) で三分探索により求めます。
3. 三分探索では、区間を3分割し、関数値が大きい方を捨てていくことで最小値の存在範囲を狭めていきます。
4. 最終的に残った候補の中から、実際に最小値を計算して答えとします。

三分探索の手順

• left = 0, right = M と初期化
• mid1 = left + (right - left) // 3
• mid2 = right - (right - left) // 3
• もし f(mid1) >= f(mid2) なら、最小値は右側にある → left = mid1
• そうでなければ左側にある → right = mid2
• 差が一定以下になったら、その区間内で全探索して最小値を求める

計算量

• 時間計算量: \(O(N \log M)\)
  • 各 \(f(x)\) の計算が \(O(N)\)、それを \(\log M\) 回程度行う。
• 空間計算量: \(O(1)\)
  • 入力を除けば定数サイズの変数のみ使用。

実装のポイント

• math.ceil(a / b) は浮動小数点誤差のリスクがあるので、整数演算で ceil(a/b) = (a + b - 1) // b とする方が安全ですが、本問題では許容誤差内に収まると仮定されています。

• 三分探索終了後に、残った区間（例えば3点程度）で実際に最小値を計算して比較する処理が必要です。

• 区間の更新条件（left = mid1 or right = mid2）に注意し、無限ループにならないよう確認しましょう。

  ソースコード

import math

def calculate_days(K, A):
    return sum(math.ceil(a / K) for a in A)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    A = list(map(int, data[3:]))
    
    # 最小日数を求めるため、x を 0 から M まで動かすが、効率的に二分探索を行う
    low = 0
    high = M
    min_days = calculate_days(K + low, A)
    
    while low <= high:
        mid = (low + high) // 2
        current_K = K + mid
        days = calculate_days(current_K, A)
        
        if mid == 0:
            min_days = min(min_days, days)
            low = mid + 1
        else:
            # 比較のために一つ前の値も計算
            prev_days = calculate_days(K + mid - 1, A)
            min_days = min(min_days, days)
            
            # 単調性を利用して探索範囲を狭める
            if days < prev_days:
                low = mid + 1
            else:
                high = mid - 1
                
    # 実際には全探索は間に合わないので、二分探索で最小値を求めることにする
    # f(x) = sum(ceil(Ai / (K+x))) は単調減少または凸関数的性質を持つため、三分探索が有効
    
    def compute_total_days(x):
        return sum(math.ceil(a / (K + x)) for a in A)
    
    left = 0
    right = M
    
    while right - left > 2:
        mid1 = left + (right - left) // 3
        mid2 = right - (right - left) // 3
        if compute_total_days(mid1) >= compute_total_days(mid2):
            left = mid1
        else:
            right = mid2
            
    answer = min(compute_total_days(x) for x in range(left, right + 1))
    print(answer)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。