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

Share

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()

Share

コメントを残す

メールアドレスが公開されることはありません。