概要

\(N\) 台の機器のうちちょうど \(K\) 台を選んで省エネモードにし、全体の消費電力を最小にする問題。

考察

この問題では、どの機器を省エネモードにすれば最も電力の合計を小さくできるかを考える必要があります。

まず、ある機器の消費電力が \(A_i\) だったとき、省エネモードにすると \(\lfloor A_i / 2 \rfloor\) になります。つまり、その機器で節約できる電力量は
$\( \text{savings}_i = A_i - \left\lfloor \frac{A_i}{2} \right\rfloor \)\( となります。したがって、「節約できる量が最も大きい機器」から \)K$ 個選んで省エネモードにすれば、最も効果的に電力の合計を下げることができます。

例えば、消費電力が [10, 8, 6] の3つの機器があり、\(K=2\) の場合を考えます。 - 各機器の節約量は [5, 4, 3] になります。 - よって、最初の2つ（節約量の多いもの）を選んで省エネモードにすると、合計は
\((10 + 8 + 6) - (5 + 4) = 24 - 9 = 15\) となり、これが最適です。

このように、節約効果の大きい順に \(K\) 個選ぶのが最適な戦略です。

素朴な方法として、毎回最大の節約量を持つ要素を探そうとすると、\(O(NK)\) の時間がかかり、\(N\) や \(K\) が大きいときに時間制限を超えてしまいます。そこで、効率的に「最大の要素を取り出す」操作を繰り返すために、優先度付きキュー（ヒープ） を使います。

Python の heapq は最小ヒープなので、最大ヒープとして使うためには、値の符号を反転させて格納します。

アルゴリズム

1. 各機器について、省エネモードにしたときの節約量 \(\text{savings}_i = A_i - \lfloor A_i / 2 \rfloor\) を計算する。
2. 全機器が通常モードであるとしたときの総消費電力 \(\text{total} = \sum_{i=1}^{N} A_i\) を求める。
3. 節約量を最大ヒープ（符号を反転させた最小ヒープ）に格納する。
4. 上位 \(K\) 個の節約量を取り出し、\(\text{total}\) から引く。
5. 最終的な \(\text{total}\) を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  （節約量の計算に \(O(N)\)、ヒープ構築に \(O(N)\)、\(K\) 回の取り出しに \(O(K \log N)\)）
• 空間計算量: \(O(N)\)
  （節約量を保存するリストとヒープ）

実装のポイント

• Python の heapq は最小ヒープなので、最大ヒープとして使うときは値をマイナスにして格納すること。

• 入力の受け取りは高速化のために sys.stdin.read を使用している。

• 総和の計算と節約量の計算は別々に行い、最後に差分を反映するのがポイント。

  ソースコード

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))
    
    # 各機器の省エネ効果（どれだけ電力が減るか）を計算
    savings = []
    for a in A:
        original = a
        saved = a - (a // 2)
        savings.append(saved)
    
    # 総和の初期値（すべての機器が通常モード）
    total = sum(A)
    
    # 省エネ効果が大きい順にK個選ぶために、最大ヒープを使う
    # heapqは最小ヒープなので、符号を反転させて使う
    heap = [-s for s in savings]
    heapq.heapify(heap)
    
    # 効果の大きい上位K個を選ぶ
    for _ in range(K):
        max_saving = -heapq.heappop(heap)
        total -= max_saving
    
    print(total)

if __name__ == "__main__":
    main()

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