概要

各機器を「半分（切り捨て）」にできる操作をちょうど \(K\) 回行うとき、合計消費電力を最小にするにはどの機器を選べばよいかを求める問題です。

考察

各機器 \(i\) の消費電力は、操作すると \(A_i \rightarrow \lfloor A_i/2 \rfloor\) に変わります。
このとき合計がどれだけ減るか（削減量）を考えるのが重要です。

機器 \(i\) の削減量は [ A_i - \lfloor A_i/2 \rfloor ] です。ここで、整数の性質より [ A_i - \lfloor A_i/2 \rfloor = \lceil A_i/2 \rceil ] が成り立ちます（偶数なら \(A_i/2\)、奇数なら \((A_i+1)/2\) だけ減る）。

つまり「どの機器に省エネモードを設定するか」は、削減量が大きい機器を \(K\) 台選ぶのが最適です。
なぜなら、各機器の操作は互いに独立で、合計の減り方は「選んだ削減量の和」になるため、最大の削減量を \(K\) 個集めれば合計が最小になります。

素朴なアプローチが難しい理由

• 「どの \(K\) 台を選ぶか」は組合せで、全探索すると \(\binom{N}{K}\) 通りになり、\(N \le 2 \times 10^5\) では到底間に合いません。
• 操作後の値そのものを比較するより、減る量（メリット）だけを比較すると一気に簡単になります。

具体例

\(A = [5, 4, 1]\) のとき - \(5 \rightarrow 2\) で削減量は \(3\)（\(\lceil 5/2 \rceil = 3\)） - \(4 \rightarrow 2\) で削減量は \(2\) - \(1 \rightarrow 0\) で削減量は \(1\)

\(K=2\) なら削減量が大きい \(3,2\) を選ぶのが最適で、合計は [ (5+4+1) - (3+2) = 10 - 5 = 5 ] となります。

アルゴリズム

1. 初期合計 \(total = \sum A_i\) を計算する。
2. 各 \(A_i\) について削減量 \(r_i = \lceil A_i/2 \rceil\) を計算する。
   整数だけで [ \lceil A_i/2 \rceil = \left\lfloor \frac{A_i+1}{2} \right\rfloor ] なので、Pythonでは (a + 1) // 2 で求まる。
3. 削減量配列を大きい順にソートし、上位 \(K\) 個の和を引く： [ total - \sum{j=1}^{K} r{(j)} ] （\(r_{(j)}\) は削減量の大きい順に並べたときの \(j\) 番目）

これで「削減できる量を最大化」＝「操作後の合計を最小化」できます。

計算量

• 時間計算量: \(O(N \log N)\)（削減量のソートが支配的）
• 空間計算量: \(O(N)\)（削減量配列を保持）

実装のポイント

• 削減量は a - (a//2) でも計算できますが、コードでは ceil(a/2) に対応する (a + 1) // 2 を使うと意図が明確です。

• 「ちょうど \(K\) 台」なので、削減量の 上位 \(K\) 個を必ず選びます（\(K\) 個未満や「最大 \(K\) 個」ではない点に注意）。

• \(N\) が大きいので、入力は sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    total = sum(A)
    reductions = [(a + 1) // 2 for a in A]  # a - floor(a/2) = ceil(a/2)
    reductions.sort(reverse=True)
    total -= sum(reductions[:K])
    print(total)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。