概要

\(N\) 個の部屋の温度を、冷却パック（1個につき \(D\) 度低下）を使ってすべて \(M\) 度以下にするために必要なパックの合計最小個数を求める問題です。

考察

この問題を解くための重要なポイントは、「各部屋を独立に考えてよい」 という点です。ある部屋に冷却パックを使っても他の部屋の温度には影響しないため、各部屋 \(i\) について「温度 \(T_i\) を \(M\) 度以下にするために必要な最小個数」を計算し、その合計を求めれば正解となります。

必要なパック数の計算

部屋 \(i\) の温度 \(T_i\) がすでに \(M\) 度以下であれば、必要なパック数は \(0\) 個です。 \(T_i\) が \(M\) 度より高い場合、少なくとも \(T_i - M\) 度分だけ温度を下げる必要があります。冷却パック1個で \(D\) 度下げられるため、必要な個数は以下のようになります。

\[(\text{必要なパック数}) = \lceil (T_i - M) / D \rceil\]

ここで \(\lceil \cdot \rceil\) は「切り上げ」を意味します。例えば、5度下げる必要があり、1パックで2度下がる場合、\(\lceil 5 / 2 \rceil = 3\) 個必要になります（2個だと4度しか下がらず、目標に届かないため）。

効率的な計算

\(N\) が最大 \(10^5\) と大きいため、1部屋ずつ順番に計算する \(O(N)\) のアルゴリズムで解く必要があります。また、温度やパックの性能 \(D\) が \(10^9\) と大きいため、1度ずつ引くようなシミュレーションではなく、割り算を使って一気に計算する必要があります。

アルゴリズム

1. 合計パック数 total_packs を \(0\) で初期化する。
2. 各部屋の温度 \(T_i\) について、以下の処理を繰り返す：
   • もし \(T_i > M\) ならば：
     • 下げるべき温度の差 \(diff = T_i - M\) を計算する。
     • 必要なパック数 \(packs\_needed = \lceil diff / D \rceil\) を計算する。
     • total_packs に \(packs\_needed\) を加算する。
3. 最終的な total_packs を出力する。

計算量

• 時間計算量: \(O(N)\)
  • 部屋の数 \(N\) に対して、各部屋の計算を定数時間で行うため、部屋数に比例した時間で終わります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の温度をリストに保持する場合、メモリは \(N\) に比例して必要になります。

実装のポイント

整数の切り上げ計算

プログラミング言語の整数型で「\(A / B\) の切り上げ」を計算する場合、浮動小数点数を使うと誤差が生じる可能性があるため、以下の整数算のテクニックを使うのが一般的です。

packs_needed = (diff + D - 1) // D

この式を使うことで、diff が D で割り切れるときは diff // D に、割り切れないときは (diff // D) + 1 になるため、正確に切り上げ結果を得ることができます。

高速な入出力

Pythonで \(N=10^5\) 程度の入力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() などで一括して読み込む方が実行時間を短縮できます。

ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, M, D を取得
    N = int(input_data[0])
    M = int(input_data[1])
    D = int(input_data[2])
    
    # 各部屋の温度 T_i を取得
    T = input_data[3:]
    
    total_packs = 0
    for i in range(N):
        temp = int(T[i])
        # 現在の温度が目標温度 M より高い場合のみ冷却パックが必要
        if temp > M:
            diff = temp - M
            # 必要な冷却パックの数は ceil(diff / D)
            # 整数切り上げの計算: (A + B - 1) // B
            packs_needed = (diff + D - 1) // D
            total_packs += packs_needed
            
    # 結果を出力
    print(total_packs)

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。