概要

各部屋の温度 \(T_i\) を冷却パック（1個で \(D\) 度下げる）で下げて、すべての部屋を \(M\) 度以下にするための最小個数を求める問題です。

考察

重要な観察は「部屋同士は独立」であることです。冷却パックは「選んだ1部屋」だけを下げるので、ある部屋に何個使うかは他の部屋に影響しません。したがって、各部屋について必要な個数を最小にして足し合わせれば全体も最小になります。

素朴に「温度が \(M\) を超えている間、1個ずつ使って \(D\) 下げる」を各部屋で繰り返すと、例えば \(T_i\) が \(10^9\) で \(D=1\) のような場合に最大 \(10^9\) 回の操作が必要になり、確実に時間切れになります（TLE）。

そこで、繰り返し操作の代わりに「何個必要か」を数式で一発計算します。
部屋 \(i\) の温度が \(T_i > M\) のとき、超過分は \(x = T_i - M\) です。この超過分を 1個あたり \(D\) ずつ減らすので、必要個数は - \(kD \ge x\) を満たす最小の整数 \(k\) つまり \(k = \left\lceil \dfrac{x}{D} \right\rceil\) です。

切り上げは整数演算で \(\displaystyle \left\lceil \frac{x}{D} \right\rceil = \frac{x + D - 1}{D} \text{ の整数除算}\) として計算できます。

また「0度未満にならない」という条件は、今回の目標が「\(M\) 以下」にすることなので、必要以上に下げる場合があっても問題なく、上の切り上げ計算でそのまま最小個数が得られます。

（例）\(M=20, D=6, T_i=35\) のとき
超過分 \(x=15\)、必要個数 \(=\lceil 15/6\rceil=3\)。3個使うと \(35 \to 29 \to 23 \to 17\) で \(20\) 以下になります。

アルゴリズム

1. 答え \(ans=0\) を用意する。
2. 各部屋について温度 \(T_i\) を見る。
   • もし \(T_i \le M\) なら何もしない（0個）。
   • もし \(T_i > M\) なら超過分 \(x=T_i-M\) を計算し、必要個数 \(\left\lceil \dfrac{x}{D}\right\rceil = \dfrac{x + D - 1}{D}\)（整数除算）を \(ans\) に加える。
3. 最後に \(ans\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各部屋を1回ずつ処理）
• 空間計算量: \(O(N)\)（入力配列を保持。読みながら処理すれば \(O(1)\) も可能）

実装のポイント

• 切り上げ除算は ceil(x/D) を浮動小数で計算せず、(x + D - 1) // D を使う（誤差防止・高速）。

• \(N\) が最大 \(10^5\) なので、Python では sys.stdin.buffer.read() などの高速入力が安全です。

• 合計個数は最大で \(N \times 10^9\) 程度になり得ますが、Python の整数は多倍長なのでオーバーフローの心配はありません。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, D = data[0], data[1], data[2]
    T = data[3:3+N]
    ans = 0
    for ti in T:
        if ti > M:
            x = ti - M
            ans += (x + D - 1) // D
    print(ans)

if __name__ == "__main__":
    main()

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