概要

不良品（内部温度が \(T\) 以上の製品）それぞれについて、「追加冷却処理をする（コスト \(C\)）」か「そのまま出荷する（損失 \(D\)）」かの安い方を選ぶことで、合計コストを最小化する問題です。

考察

重要な気づき

この問題では、各製品は独立に判断できます。つまり、ある製品に冷却処理を施すかどうかは、他の製品の選択に一切影響しません。

製品を以下の2種類に分類して考えます。

• 内部温度が \(T\) 未満の製品: もともと不良品ではないので、何もしなくてもコスト \(0\) です。冷却処理を施すと無駄にコスト \(C\) がかかるだけなので、何もしないのが最適です。
• 内部温度が \(T\) 以上の製品（不良品）: 2つの選択肢があります。
  • 追加冷却処理を施す → コスト \(C\) が発生
  • そのまま出荷する → 損失 \(D\) が発生

不良品1個あたり、\(C\) と \(D\) のうち小さい方を選べばよいです。

具体例

例えば \(N=4, T=50, C=3, D=5\) で、内部温度が \(W = [30, 60, 80, 40]\) の場合を考えます。

製品	温度	不良品？	最適な選択	コスト
1	30	No	何もしない	0
2	60	Yes	冷却処理（\(\min(3,5) = 3\)）	3
3	80	Yes	冷却処理（\(\min(3,5) = 3\)）	3
4	40	No	何もしない	0

合計コストは \(0 + 3 + 3 + 0 = 6\) となります。

もし \(C = 7, D = 5\) であれば、不良品はそのまま出荷した方が安い（\(\min(7,5) = 5\)）ので、1個あたり損失 \(5\) を受け入れます。

素朴なアプローチで問題ないか

\(N\) 個の製品を1回ずつ見て判定するだけなので、\(O(N)\) で十分高速です。組み合わせを全列挙するような方法（\(2^N\) 通り）は不要です。

アルゴリズム

1. 各製品 \(i\) について、内部温度 \(W_i\) が \(T\) 以上かどうかを判定する。
2. \(W_i \geq T\)（不良品）であれば、\(\min(C, D)\) を合計に加算する。
3. \(W_i < T\) であれば、コストは \(0\) なので何もしない。
4. 最終的な合計値を出力する。

計算量

• 時間計算量: \(O(N)\) — 全製品を1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の配列を保持する分（逐次読み込みにすれば \(O(1)\) も可能）

実装のポイント

• \(C, D\) ともに最大 \(10^9\)、不良品の数は最大 \(2 \times 10^5\) 個なので、合計値は最大 \(2 \times 10^{14}\) 程度になります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 内部温度が \(T\) 未満の製品に冷却処理を施しても問題文上は許されますが、コストが無駄に増えるだけなので、不良品にのみ判定を行えば十分です。

  ソースコード

N, T, C, D = map(int, input().split())
W = list(map(int, input().split()))

total = 0
for w in W:
    if w >= T:
        total += min(C, D)

print(total)

---

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