AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 141 D – Powerful Discount Tickets
一枚使うたびに半額に出来る強力な割引券ということで、Powerful Discount Ticketsという名前の問題。ただ、discount ticketsといった時には、早期割引航空券や映画の前売券などのように、「値段が割り引かれた券」という意味合いがどちらかというと強い気も……。ここはcouponとかvoucherという単語のほうが分かりやすかったのではないかと思う。
それはさておき。
優先度付きキュー (heapq) を知っていれば、解法を思いつくのにさほど苦労はしないだろう。知らなければ、ここで覚えておいたほうがよい。
# AtCoder Beginner Contest 141 D - Powerful Discount Tickets
# https://atcoder.jp/contests/abc141/tasks/abc141_d
# tag: 優先度付きキュー 典型問題 高橋君
# 優先度付きキューを知っていれば簡単に解けるが、
# 知らなければ解くのが困難になる、典型問題。
# 要するに、割引券を使うごとに品物が半額になる。
# 割引券の枚数が一定であることを考えると、
# ある割引券をどの品物に使用するかを考えたとき、
# もっとも高い品物に対して使用したい。
# 値段を調べる → 一番高い品物に割引券を使う →
# 値段を調べる → 一番高い……とループさせるわけだが、
# そのままだと計算量が O(MN) となってしまうので、
# 制約 (1 <= N, M <= 10^5) からすると間に合わない。
# が、ここで優先度付きキューを使用すると、O(M logN) で
# 解くことができるので、間に合う。みたいな。
import heapq
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 優先度付きキューは小さい順に出てくるため、
# あらかじめ値を負にしておく
items = [-v for v in A]
heapq.heapify(items)
# そのまま //2 すると、負の値で切り捨てがずれるので注意。
# そのため、一旦きちんと正の値に戻してから処理をする。
# ここで切り捨ててもいい根拠については、
# 一般に正の整数 x, a, b について
# (x // a) // b == x // (a * b) となるためだが、
# 厳密な証明は省略。ごく単純に考えるなら、整数演算ではなく
# 有理数演算として捉えた場合、余りは全て小数部に落ちる
# ことになるが、それは当然 0 <= r < 1 の範囲に留まるため……
# みたいな雑な理解でもいいかもしれない。
for _ in range(M):
max_price = -heapq.heappop(items)
heapq.heappush(items, -(max_price//2))
result = -sum(items)
print(result)
main()
関連
