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) を知っていれば、解法を思いつくのにさほど苦労はしないだろう。知らなければ、ここで覚えておいたほうがよい。

[pastacode lang=”python” user=”scrblbug” repos=”atcoder” path_id=”python/abc141_d.py” revision=”” highlight=”” lines=”” provider=”github”/]

Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です