概要

\(N\) 台の機器のうちちょうど \(K\) 台を選んで消費電力を半分（小数点以下切り捨て）にするとき、全体の消費電力の合計を最小化する問題です。

考察

全体の消費電力を最小化するためには、「省エネモードに設定することで、どれだけ電力を減らせるか」という「削減量」に着目するのがポイントです。

各機器 \(i\) について、省エネモードに設定したときに削減される電力 \(D_i\) は以下の式で表せます。 $\(D_i = A_i - \lfloor A_i / 2 \rfloor\)$

例えば、\(A_i = 13\) の場合、省エネモード後の電力は \(\lfloor 13 / 2 \rfloor = 6\) となり、削減量は \(13 - 6 = 7\) です。

この問題では「ちょうど \(K\) 台」を省エネモードにする必要があります。全体の合計を最も小さくするには、この削減量 \(D_i\) が大きいものから順に \(K\) 台選ぶのが最善です。各機器に対して省エネモードを設定できるのは最大 1 回までという制約があるため、単純に削減量を計算して比較する「貪欲法」の考え方が適用できます。

アルゴリズム

以下の手順で解くことができます。

1. 各機器 \(i\) について、削減量 \(D_i = A_i - (A_i // 2)\) を計算し、リストに格納する。
2. 削減量のリストを降順（大きい順）にソートする。
3. リストの先頭から \(K\) 個の要素の和を求める。これが「削減できる電力の最大合計」となる。
4. 全機器の初期の消費電力の合計から、3で求めた最大削減量を引いた値を出力する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 削減量の計算に \(O(N)\)、削減量リストのソートに \(O(N \log N)\)、合計の計算に \(O(N)\) かかります。制約の \(N = 2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力データや削減量を格納するリストのために \(O(N)\) のメモリを使用します。

実装のポイント

• 整数除算: Python では // 演算子を使うことで、正の数に対して小数点以下を切り捨てた整数値（floor）を取得できます。

• 高速な入力: \(N\) が大きいため、input() を繰り返すよりも sys.stdin.read().split() などを用いて一括で読み込む方が実行時間を短縮できます。

• 大きな値の扱い: 最終的な合計値は \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\) 程度になる可能性がありますが、Python は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に処理するのに適しています
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # 1番目の要素は機器の台数 N、2番目の要素は省エネモードに設定する台数 K
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 3番目以降の要素は各機器の消費電力 A_i
    # 全ての A_i を整数のリストに変換
    a = list(map(int, input_data[2:]))
    
    # 各機器を省エネモードにしたときに削減できる電力を計算する
    # 消費電力 A_i の機器を省エネモードにすると floor(A_i / 2) になるため、
    # 削減される電力は A_i - floor(A_i / 2) となる。
    # Pythonの // 演算子は正の数に対して小数点以下を切り捨てる（floor）動作をする。
    reductions = [x - (x // 2) for x in a]
    
    # 全体の消費電力を最小化するためには、削減できる電力を最大化すればよい。
    # 削減量のリストを降順（大きい順）にソートする。
    reductions.sort(reverse=True)
    
    # 全機器の初期の消費電力の合計を計算
    total_initial_power = sum(a)
    
    # 削減量が大きい方から K 台分の削減量を合計する
    # スライス reductions[:k] を使うことで、上位 K 個の要素を取得できる。
    max_total_reduction = sum(reductions[:k])
    
    # 最終的な消費電力の合計 = (初期の合計) - (最大化された削減量の合計)
    print(total_initial_power - max_total_reduction)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。