概要

\(N\) 台の機器からちょうど \(K\) 台を選んで省エネモード（消費電力を半分に切り捨て）を設定し、全機器の消費電力の合計を最小化する問題です。

考察

重要な気づき：削減量に注目する

省エネモードを設定すると、消費電力は \(A_i\) から \(\lfloor A_i / 2 \rfloor\) に変わります。

このとき、削減される電力量は： $\(A_i - \lfloor A_i / 2 \rfloor = \lceil A_i / 2 \rceil = \frac{A_i + 1}{2}\)$

例えば： - \(A_i = 10\) の場合：削減量 \(= 10 - 5 = 5\) - \(A_i = 7\) の場合：削減量 \(= 7 - 3 = 4\) - \(A_i = 1\) の場合：削減量 \(= 1 - 0 = 1\)

貪欲法が最適

合計消費電力を最小化したいので、削減量が大きい機器から優先的に省エネモードを設定すればよいです。

これは直感的にも明らかです。例えば、削減量が \([5, 4, 3, 2, 1]\) の5台から \(K=2\) 台選ぶなら、削減量 \(5\) と \(4\) の機器を選ぶのが最も合計を減らせます。

なぜ貪欲法で正しいか

• 各機器に省エネモードを設定するかどうかは独立した選択
• 省エネモードを設定できる回数は各機器に対して最大1回
• どの機器を選んでも、他の機器への影響はない

このような状況では、単純に削減量の大きい順に \(K\) 個選べば最適解が得られます。

アルゴリズム

1. 各機器の削減量 \(A_i - \lfloor A_i / 2 \rfloor\) を計算する
2. 削減量が大きい順に \(K\) 個を選ぶ
3. 元の合計消費電力から、選んだ \(K\) 個の削減量の合計を引く

具体例

\(N = 4, K = 2, A = [10, 7, 3, 1]\) の場合：

機器	消費電力 \(A_i\)	省エネ後	削減量
1	10	5	5
2	7	3	4
3	3	1	2
4	1	0	1

削減量の大きい順に2個選ぶと、機器1と機器2（削減量 \(5 + 4 = 9\)）

答え：\(10 + 7 + 3 + 1 - 9 = 12\)

計算量

• 時間計算量: \(O(N \log K)\)
  • 削減量の計算：\(O(N)\)
  • 上位 \(K\) 個の選択（heapq.nlargest）：\(O(N \log K)\)
• 空間計算量: \(O(N)\)
  • 削減量を格納する配列

実装のポイント

1. 削減量の計算

   reduction = a - a // 2  # これは (a + 1) // 2 と同じ
   

   Python の // は切り捨て除算なので、\(\lfloor A_i / 2 \rfloor\) を正しく計算できます。

2. 上位K個の効率的な取得

   heapq.nlargest(K, reductions)
   

   heapq.nlargest を使うと、全体をソートするより効率的に上位 \(K\) 個を取得できます（特に \(K\) が \(N\) より十分小さい場合）。

3. 整数オーバーフローの心配なし Python は任意精度整数をサポートしているため、\(A_i \leq 10^9\) でも合計が大きくなってもオーバーフローの心配はありません。

   ソースコード

import heapq

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 省エネモードを設定すると、消費電力は A_i から floor(A_i / 2) になる
    # 削減量は A_i - floor(A_i / 2) = ceil(A_i / 2) = (A_i + 1) // 2
    # 合計を最小化するには、削減量が大きい機器から省エネモードを設定すればよい
    
    # 削減量を計算
    reductions = []
    for a in A:
        reduction = a - a // 2  # = (a + 1) // 2
        reductions.append(reduction)
    
    # 削減量が大きい順にK個選ぶ
    # heapqを使って上位K個の削減量を求める
    largest_reductions = heapq.nlargest(K, reductions)
    
    total = sum(A)
    total -= sum(largest_reductions)
    
    print(total)

solve()

---

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