概要

各エリアに必要な作業回数の合計を求め、高橋君のチームの作業上限 \(M\) を超えた分だけ青木君に応援を要請する問題です。

考察

必要な作業回数の計算

\(i\) 番目のエリアには \(A_i\) 脚の椅子があり、1 回の作業で最大 \(K\) 脚運べるので、そのエリアに必要な作業回数は \(\lceil A_i / K \rceil\)（切り上げ除算）です。

例えば、\(A_i = 10\), \(K = 3\) の場合、\(\lceil 10 / 3 \rceil = 4\) 回の作業が必要です（3 + 3 + 3 + 1 = 10）。

応援要請の最小回数

すべてのエリアの作業回数の合計を \(T = \displaystyle\sum_{i=1}^{N} \lceil A_i / K \rceil\) とします。

• 高橋君のチームは最大 \(M\) 回の作業をこなせます。
• 青木君も 1 回の応援要請で 1 回の作業（同じルール：最大 \(K\) 脚を同一エリアに）を行います。

ここで重要な気づきは、高橋君の作業も青木君の作業もまったく同じルールに従うということです。つまり、青木君の 1 回の作業は高橋君チームの 1 回の作業と同等であり、作業の割り当て方を工夫しても合計必要回数 \(T\) は変わりません。

したがって、応援要請の最小回数は単純に：

\[\text{答え} = \max(0, \, T - M)\]

です。\(T \leq M\) なら高橋君のチームだけで完了できるので \(0\) を出力します。

素朴なアプローチとの比較

この問題は一見、各エリアへの作業割り当てを最適化する必要がありそうに見えますが、実際には作業のルールが同一であるため、単に「全体の必要作業回数 − チームの上限」を計算するだけで済みます。特別な最適化やデータ構造は不要です。

アルゴリズム

1. 各 \(A_i\) に対して \(\lceil A_i / K \rceil\) を計算し、合計 \(T\) を求める。
2. \(T - M > 0\) なら \(T - M\) を出力、そうでなければ \(0\) を出力。

切り上げ除算は、整数演算で \(\lceil A_i / K \rceil = \lfloor (A_i + K - 1) / K \rfloor\) として計算できます。

具体例

\(N = 3\), \(M = 5\), \(K = 4\), \(A = [10, 7, 3]\) の場合：

• エリア 1: \(\lceil 10/4 \rceil = 3\) 回
• エリア 2: \(\lceil 7/4 \rceil = 2\) 回
• エリア 3: \(\lceil 3/4 \rceil = 1\) 回
• 合計 \(T = 6\) 回
• 答え: \(\max(0, 6 - 5) = 1\) 回

計算量

• 時間計算量: \(O(N)\) — 各エリアの作業回数を 1 回ずつ計算して合計するだけ
• 空間計算量: \(O(N)\) — 配列 \(A\) の格納（ストリーム処理にすれば \(O(1)\) も可能）

実装のポイント

• \(N\) が最大 \(10^6\)、\(A_i\) が最大 \(10^9\)、\(K\) が最小 \(1\) のとき、合計 \(T\) は最大 \(10^{15}\) 程度になるため、64 ビット整数が必要です。Python では整数のオーバーフローがないため心配不要ですが、C++ などでは long long を使う必要があります。

• sys.stdin.read() で一括読み込みすることで、\(N\) が大きい場合の入力処理を高速化しています。

• 切り上げ除算は (a + K - 1) // K で正しく計算できます（\(a \geq 1\), \(K \geq 1\) のとき）。

  ソースコード

import sys
import math

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    total = 0
    for a in A:
        total += (a + K - 1) // K
    
    ans = total - M
    if ans < 0:
        ans = 0
    print(ans)

main()

---

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