概要

\(N\) 件の届け先に荷物を届ける際、1日あたりの配送能力を \(K\) から最大 \(K+M\) まで増やせるとき、全体の配送日数 \(\sum_{i=1}^{N} \lceil A_i / (K+x) \rceil\) を最小化する問題です。

考察

重要な気づき：配送能力を上げれば日数は減る（増えない）

この問題の核心は、天井関数 \(\lceil A_i / c \rceil\) が \(c\)（配送能力）に対して単調非増加であるという性質です。

具体例で確認しましょう。\(A_i = 10\) のとき：

配送能力 \(c\)	\(\lceil 10 / c \rceil\)
3	4
4	3
5	2
10	1
11	1

配送能力 \(c\) を大きくすると、1回の訪問で届けられる荷物が増えるため、必要な訪問回数は減る（または変わらない）ことが分かります。

各届け先について成り立つなら、合計でも成り立つ

各 \(\lceil A_i / c \rceil\) が \(c\) に対して単調非増加であれば、その合計 \(\sum_{i=1}^{N} \lceil A_i / c \rceil\) も \(c\) に対して単調非増加です。

結論

合計日数は配送能力 \(c = K + x\) が大きいほど小さくなる（または変わらない）ので、\(x\) を最大値 \(M\) に設定するのが常に最適です。

つまり、難しい探索や二分探索は一切不要で、\(c = K + M\) として合計日数を計算するだけで答えが得られます。

アルゴリズム

1. 配送能力を \(c = K + M\) とする。
2. 各届け先 \(i\) について、必要日数 \(\lceil A_i / c \rceil\) を計算する。
   • 天井除算は \((A_i + c - 1) / c\) の整数除算（切り捨て）で求められる。
3. すべての届け先の日数を合計して出力する。

天井除算の補足

\(\lceil a / b \rceil\)（\(a, b\) は正の整数）は、次の式で計算できます：

\[\lceil a / b \rceil = \lfloor (a + b - 1) / b \rfloor\]

例えば \(a = 10, b = 3\) のとき、\((10 + 3 - 1) / 3 = 12 / 3 = 4 = \lceil 10/3 \rceil\) となり正しく計算できます。

計算量

• 時間計算量: \(O(N)\) — 各届け先について天井除算を1回行うだけ
• 空間計算量: \(O(N)\) — 配列 \(A\) の格納

実装のポイント

• \(K, M, A_i\) がそれぞれ最大 \(10^9\) なので、\(K + M\) は最大 \(2 \times 10^9\) になります。Python では整数オーバーフローの心配はありませんが、C++ などでは long long を使う必要があります。

• 天井除算を math.ceil(A_i / c) で行うと浮動小数点誤差が生じる可能性があるため、整数演算 (A_i + c - 1) // c を使うのが安全です。

• 問題文を読んで「最適な \(x\) を探索する必要があるのでは？」と思いがちですが、単調性に気づけば \(x = M\) が最適と即座に分かります。

  ソースコード

import sys

def compute_days(A, cap):
    total = 0
    for a in A:
        total += (a + cap - 1) // cap
    return total

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # We want to minimize sum of ceil(A_i / (K+x)) for x in [0, M]
    # As x increases (capacity increases), total days decrease or stay same.
    # So the minimum is achieved at x = M.
    # Wait, that's not necessarily optimal if the function is monotonically non-increasing...
    # Actually, ceil(A_i / c) is non-increasing in c, so the sum is non-increasing in c.
    # Therefore x = M always gives the minimum.
    
    # But wait, let me reconsider. The problem says "find the minimum days when x is chosen optimally".
    # Since increasing capacity can only decrease or maintain the number of days for each destination,
    # the optimal is simply x = M.
    
    cap = K + M
    print(compute_days(A, cap))

solve()

---

この解説は claude4.6opus-thinking によって生成されました。