概要

\(N\) 個の部屋から \(K\) 個を選び、それぞれの室温を適切な範囲 \([L, R]\) に調整するための最小コストを求める問題です。各部屋の調整コストを計算し、コストが小さい順に \(K\) 個選ぶ貪欲法で解けます。

考察

重要な気づき

1. 各部屋のコストは独立に計算できる

   • 部屋 \(i\) の室温 \(T_i\) を範囲 \([L, R]\) 内に調整するコストは、他の部屋の状態に依存しません

2. 最小コストで調整する方法

   • \(T_i < L\) の場合：\(L\) まで上げるのが最小コスト → コストは \(L - T_i\)
   • \(T_i > R\) の場合：\(R\) まで下げるのが最小コスト → コストは \(T_i - R\)
   • \(L \leq T_i \leq R\) の場合：調整不要 → コストは \(0\)

3. どの \(K\) 個を選ぶべきか

   • 総コストを最小化したいので、コストが小さい部屋から優先的に選べばよい

具体例

例えば、\(N=5\), \(K=3\), \(L=20\), \(R=25\), \(T = [15, 22, 30, 18, 24]\) の場合： - 部屋1: \(T_1=15 < 20\) → コスト \(= 20 - 15 = 5\) - 部屋2: \(T_2=22\) は範囲内 → コスト \(= 0\) - 部屋3: \(T_3=30 > 25\) → コスト \(= 30 - 25 = 5\) - 部屋4: \(T_4=18 < 20\) → コスト \(= 20 - 18 = 2\) - 部屋5: \(T_5=24\) は範囲内 → コスト \(= 0\)

コストをソート: \([0, 0, 2, 5, 5]\)

小さい順に3個選ぶと、コストは \(0 + 0 + 2 = 2\) となります。

アルゴリズム

1. 各部屋について、室温を範囲 \([L, R]\) に調整するためのコストを計算する
2. コストの配列を昇順にソートする
3. ソートした配列の先頭から \(K\) 個の和を求める

この方法は貪欲法と呼ばれ、「局所的に最良の選択を繰り返すことで、全体的に最良の解を得る」手法です。本問題では、コストが小さい部屋から選ぶことが常に最適であることが保証されています。

計算量

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

  • 各部屋のコスト計算: \(O(N)\)
  • ソート: \(O(N \log N)\)
  • 先頭 \(K\) 個の和: \(O(K) \subseteq O(N)\)

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

  • コストを格納する配列に \(O(N)\)

実装のポイント

• 室温 \(T_i\) と範囲 \(L, R\) が負の値を取りうる（\(-10^9\) まで）ことに注意。ただし、コストは必ず非負になるため、特別な処理は不要

• コストの最大値は \(2 \times 10^9\) 程度、\(K\) 個の和は最大で \(2 \times 10^{14}\) 程度になりうるため、32ビット整数ではオーバーフローする可能性がある。Pythonでは整数のオーバーフローを気にする必要がない

• costs.sort() でソートした後、スライス costs[:K] で先頭 \(K\) 個を取り出すのがPythonらしい書き方

  ソースコード

def solve():
    N, K, L, R = map(int, input().split())
    T = list(map(int, input().split()))
    
    # 各部屋のコストを計算
    # 室温がL以上R以下なら0、Lより低ければL-Ti、Rより高ければTi-R
    costs = []
    for t in T:
        if t < L:
            costs.append(L - t)
        elif t > R:
            costs.append(t - R)
        else:
            costs.append(0)
    
    # コストが小さい順にK個選ぶ
    costs.sort()
    print(sum(costs[:K]))

solve()

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