概要

各エリアで必要な作業回数 \(\lceil A_i / K \rceil\) を合計し、その合計がチームの上限 \(M\) を何回超えるか（超えた分が応援要請回数）を求める問題です。

考察

• 1 回の作業で運べる椅子は最大 \(K\) 脚で、しかも同一エリアにしか運べません。
  よって、エリア \(i\) の椅子 \(A_i\) 脚を並べるのに必要な作業回数は、端数が出たらもう 1 回必要なので \(\lceil A_i / K \rceil\) 回になります。
• 全エリアの必要作業回数は $\( T = \sum_{i=1}^{N} \left\lceil \frac{A_i}{K} \right\rceil \)$ で確定です。どの作業を誰（高橋チーム or 青木）に割り当てるかは自由なので、「合計で何回の作業が必要か」さえ分かれば十分です。
• 高橋君のチームは最大 \(M\) 回まで担当でき、残りを青木君が 1 回の応援要請につき 1 回担当してくれます。
  したがって最小の応援要請回数は $\( \max(0,\, T - M) \)$ となります。
• 素朴に「作業を実際にシミュレーションして割り当てる」必要はありません（そもそも最適な割り当てを考える問題ではなく、合計回数が決まっているため）。
  また \(N \le 10^6\) なので、各 \(A_i\) について定数時間で処理して 1 回走査するのが安全です。

具体例：\(K=3, (A_1,A_2)=(7,3)\) のとき
\(\lceil 7/3\rceil=3,\ \lceil 3/3\rceil=1\) なので合計 \(T=4\) 回。
もし \(M=2\) なら不足は \(4-2=2\) 回で、応援要請は 2 回が最小です。

アルゴリズム

1. 入力 \(N, M, K\) を読む。
2. \(total=0\) とし、各 \(A_i\) について $\( total \mathrel{+}= \left\lceil \frac{A_i}{K} \right\rceil \)\( を加算する。切り上げは整数演算で \)\( \left\lceil \frac{A_i}{K} \right\rceil = \left\lfloor \frac{A_i + K - 1}{K} \right\rfloor \)$ を使う。
3. \(ans = total - M\) を計算し、\(ans<0\) なら \(0\) にする。
4. \(ans\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各エリアを 1 回ずつ処理）
• 空間計算量: \(O(1)\)（入力配列を保持せず逐次処理）

実装のポイント

• \(\lceil A_i / K \rceil\) は浮動小数点を使わず、\((A_i + K - 1) // K\) で正確に求める。

• \(N\) が最大 \(10^6\) と大きいので、Python では高速入力が重要です。提示コードのように sys.stdin.buffer.read() でまとめて読み、整数パースする方法が有効です。

• 合計 \(total\) は最大でおおよそ \(10^6 \times 10^9 = 10^{15}\) 程度になり得るため、十分大きい整数を扱える型（Python の int）で問題ありません。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n = len(data)
idx = 0

def next_int():
    global idx
    while idx < n and data[idx] <= 32:
        idx += 1
    num = 0
    while idx < n and data[idx] > 32:
        num = num * 10 + (data[idx] - 48)
        idx += 1
    return num

N = next_int()
M = next_int()
K = next_int()

total = 0
for _ in range(N):
    a = next_int()
    total += (a + K - 1) // K

ans = total - M
if ans < 0:
    ans = 0
sys.stdout.write(str(ans))

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