概要

各部屋の温度を目標温度 \(M\) 度以下にするために、それぞれの部屋で必要な冷却パックの個数を計算し、合計を求める問題です。

考察

重要な気づき

1. 部屋ごとに独立して考えられる: ある部屋で使った冷却パックは他の部屋に影響しないため、各部屋で必要な冷却パック数を個別に計算して合計すればよいです。

2. すでに条件を満たしている部屋: 現在の温度 \(T_i\) が目標温度 \(M\) 以下の部屋は、冷却パックを使う必要がありません。

3. 必要なパック数の計算: 温度 \(T_i > M\) の部屋では、温度を \((T_i - M)\) 度以上下げる必要があります。1個のパックで \(D\) 度下げられるので、必要なパック数は \((T_i - M) \div D\) の切り上げになります。

具体例

• \(T_i = 30\) 度、\(M = 25\) 度、\(D = 3\) 度の場合
• 下げる必要がある温度: \(30 - 25 = 5\) 度
• 必要なパック数: \(\lceil 5 \div 3 \rceil = \lceil 1.67 \rceil = 2\) 個
• （1個だと3度しか下がらず27度、2個で6度下がって24度になり、目標達成）

なぜ切り上げが必要か

温度をちょうど \(M\) 度にする必要はなく、\(M\) 度以下にすればよいです。しかし、\((T_i - M)\) が \(D\) で割り切れない場合、端数分も下げる必要があるため、パック数は切り上げで計算します。

アルゴリズム

1. 各部屋 \(i\) について以下を行う：
   • \(T_i \leq M\) なら、その部屋には冷却パック不要（0個）
   • \(T_i > M\) なら、必要なパック数 \(= \lceil (T_i - M) / D \rceil\) を計算
2. すべての部屋で必要なパック数を合計して出力

切り上げの計算方法

Pythonでは math.ceil() 関数を使うことで、小数の切り上げを簡単に計算できます。

import math
packs_needed = math.ceil((t - M) / D)

整数演算のみで行う場合は以下の式も使えます：

packs_needed = (t - M + D - 1) // D

計算量

• 時間計算量: \(O(N)\)
  • 各部屋に対して定数時間の計算を行うため
• 空間計算量: \(O(N)\)
  • 温度のリストを保持するため（逐次処理すれば \(O(1)\) も可能）

実装のポイント

• 条件分岐を忘れない: \(T_i \leq M\) の場合は冷却パックが不要なので、\(T_i > M\) のときだけ計算します。負の値を計算してしまうと間違った答えになります。

• 整数オーバーフローに注意: 制約より \(T_i\) や \(M\) は最大 \(10^9\) になりますが、Pythonでは整数のオーバーフローは発生しないため、特別な対処は不要です。

• 0度未満にならない制約: 問題文に「0度未満にはならない」とありますが、目標は \(M\) 度以下にすることなので、この制約は最小パック数の計算には影響しません。

  ソースコード

import math

def solve():
    N, M, D = map(int, input().split())
    T = list(map(int, input().split()))
    
    total_packs = 0
    for t in T:
        if t > M:
            # 温度をM以下にするために必要なパック数
            # (t - M) / D の切り上げ
            packs_needed = math.ceil((t - M) / D)
            total_packs += packs_needed
    
    print(total_packs)

solve()

---

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