概要

\(0 \le x \le M\) の範囲で 1 日の配送能力を \(K+x\) に変更できるとき、全体の必要日数 \(\sum_{i=1}^{N}\left\lceil \frac{A_i}{K+x}\right\rceil\) を最小にする日数を求めます。

考察

重要な観察は「1 日に運べる個数（分母）を増やすと、必要日数は増えない」という単調性です。

• 各届け先 \(i\) の必要日数は \(f_i(d)=\left\lceil \frac{A_i}{d}\right\rceil\)（ここで \(d=K+x\)）です。
• \(d\) を大きくすると 1 日に運べる量が増えるので、\(\frac{A_i}{d}\) は小さくなります。したがって切り上げても値は 同じか小さくなる だけで、増えることはありません。
  • 例：\(A_i=10\) のとき
    \(d=3 \Rightarrow \lceil 10/3\rceil=4\)
    \(d=4 \Rightarrow \lceil 10/4\rceil=3\)
    \(d=5 \Rightarrow \lceil 10/5\rceil=2\)

よって全体の和 $\( F(d)=\sum_{i=1}^{N}\left\lceil \frac{A_i}{d}\right\rceil \)\( も \)d\( に対して単調非増加です。つまり、許される範囲で \)d\( を最大にしたとき（\)x$ を最大にしたとき）が最小になります。

• 結論：最適な選択は常に \(x=M\)（能力を最大まで上げる）です。

素朴に \(x=0,1,2,\dots,M\) を全探索すると、\(M \le 10^9\) なので到底間に合いませんが、上の単調性により探索自体が不要になります。

アルゴリズム

1. 最大の配送能力 \(C = K + M\) を計算する。
2. 答えを $\( \sum_{i=1}^{N}\left\lceil \frac{A_i}{C}\right\rceil \)$ として求める。
3. 切り上げは整数演算で $\( \left\lceil \frac{a}{C}\right\rceil = \left\lfloor \frac{a + C - 1}{C}\right\rfloor \)$ を使う（Python では (a + C - 1) // C）。

計算量

• 時間計算量: \(O(N)\)（各 \(A_i\) を 1 回ずつ処理するだけ）
• 空間計算量: \(O(1)\)（入力を逐次処理すれば追加配列不要）

実装のポイント

• 切り上げ除算は (a + C - 1) // C を使うと安全かつ高速です。

• \(N\) が最大 \(2\times 10^5\) なので、Python では sys.stdin.buffer.read() による高速入力が有効です。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    K = next(it)
    M = next(it)
    C = K + M
    ans = 0
    for _ in range(N):
        a = next(it)
        ans += (a + C - 1) // C
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。