概要

各製品の内部温度に基づいて、冷却処理のコストと不良品による損失の合計を最小化する問題です。

考察

この問題では、各製品の内部温度 \(W_i\) が閾値 \(T\) 以上であれば「不良品」となり、出荷すると損失 \(D\) が発生します。しかし、冷却処理を行うことで損失を回避できます。冷却にはコスト \(C\) がかかります。

各不良品ごとに「冷却する（コスト \(C\)）」か「冷却せずに損失を受け入れる（損失 \(D\)）」かを選ぶことができるので、単純に考えると「冷却するかしないか」を全パターン試すといった素朴な方法では、計算量が爆発してしまいます（例：\(2^N\)通り）。しかし、各製品における選択は独立しているため、それぞれの不良品に対して「コスト \(C\) と損失 \(D\) のうち小さい方を選ぶ」のが最適です。

つまり、各不良品に対して \(\min(C, D)\) を足し合わせたものが答えになります。

また、内部温度が \(T\) 未満の製品は不良品ではないので、冷却する必要も損失も発生しないため、これらは無視して良いです。

例えば、以下のような入力があったとします：

N=3, T=5, C=2, D=3
W = [4, 6, 7]

• 製品1: 温度4 → 不良品ではない → 何もしない
• 製品2: 温度6 → 不良品 → 冷却(2) or 損失(3) → 冷却がお得
• 製品3: 温度7 → 不良品 → 冷却(2) or 損失(3) → 冷却がお得

合計コスト = 2 + 2 = 4

アルゴリズム

1. 内部温度が \(T\) 以上の製品（不良品候補）だけを抽出する。
2. 抽出した各製品に対し、「冷却コスト \(C\)」と「損失 \(D\)」のうち小さい方を選択する。
3. それらの和を取ったものを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。
• 不良品でない製品は無視して良いので、最初にフィルタリングすることで効率よく処理できる。
• 各不良品について独立に判断できるため、ループ内で min(C, D) を足し合わせるだけでよい。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    C = int(data[2])
    D = int(data[3])
    W = list(map(int, data[4:]))

    # 不良品となる製品のみを抽出（W_i >= T）
    defective = [w for w in W if w >= T]
    
    # 不良品がなければコストは0
    if not defective:
        print(0)
        return
    
    # コスト比較：冷却処理(C) vs 損失(D)
    # 各不良品について、冷却するかしないかの選択がある
    # 冷却コスト C と 損失 D のどちらがお得か比較
    total_cost = 0
    for _ in defective:
        total_cost += min(C, D)
    
    print(total_cost)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。