Python3で解く AtCoder Beginner Contest 141 D - Powerful Discount Tickets

リスト内のmaxの値が必要なパターン。
これをそのままやらずに、優先度付キューを使う。 Pythonのheapqは最小値をpopするので注意。

概要
解くときに考えた内容
コード

概要

$N$ 個商品がある。
$M$ 枚商品券がある。
$A$ 円の商品に商品券を $Y$ 枚使うと商品の値段が $\frac{A}{2^Y}$ （切り捨て）になる。
全部買うので、最も安くなるように商品券をつかうといくらで買える？

解くときに考えた内容

商品券を使って、都度、値段が一番高いものについて商品券を使うを繰り返せばいい。大きい値に商品券を使うことが一番効果が高いから。
ただ、同じ商品が ${2^Y}$ で割ったときに余りが一気に複数枚商品券を使った場合と１枚ずつ使った場合に結果が同じになること自体が自明ではない気がするのでそれを考える。

ちゃんとした証明ではないが、とりあえず分けてもまとめても同じだけ使えば最終的には同じ値になる。

2回に分けた場合： $\frac{2m+1}{2}$ → $m + \frac{1}{2}$ → $m$ → $\frac{m}{2}$
1回でまとめた場合： $\frac{2m+1}{2^2}$ → $\frac{m}{2}+ \frac{1}{2^2}$ → $\frac{m}{2}$

最初リストのmaxをとってTLEだして、こういうときは優先度付きキューぢゃんと思い出せた。それにしてもPythonで実装されているheapqは最も小さい値を返すから、いちいち符号を変えてやらないといけなくて、他にいい方法はないのだろうか。

コード

from heapq import heapify, heappush, heappop

def main():
    n, m = map(int, input().split())
    a = [int(x)*-1 for x in input().split()]
    ans = sum(a)*-1
    diff = 0
    
    heapify(a)
    for _ in range(1, m+1):
        _h_a = heappop(a) * -1
        diff += _h_a - _h_a // 2
        heappush(a, (_h_a // 2)*-1)
    ans -= diff
    print(ans)

    # ミスった、そもそもリストのmaxとるならheapqつかへ
    # a.sort(reverse=True)
    # ans = sum(a)
    # diff = 0
    # for i in range(1, m+1):
    #     a_i = a[:i]
    #     a_m = max(a_i)
    #     diff += a_m  - a_m // 2
    #     a_m_i = a_i.index(a_m)
    #     a[a_m_i] = a[a_m_i] // 2
    # ans -= diff
    # print(ans)
    
if __name__ == '__main__':
    main()