【C#】AtCoder Beginner Contest 141のD問題でハマったポイント
今回の記事は、ABC141で、D問題が解けずにハマったので、復習してわかったポイントを自分用にまとめようと思います。
D問題の内容
- N個の品物を1個ずつ順番に購入
- i番目の値段はA_i
- M枚の割引券を使用可能
- 割引券をY枚使うと1/2yの割引が可能
最小で何円あればすべての商品を買うことができるか
考えた解法と実装
支払う金額を最小にする。ということから、与えられた金額の中で最大の金額に割引を使用ればよいと考えました。実際にそのとおりで間違っていないのですが、例えば、金額を配列に格納→降順にソート→最大の金額を割引したあとの値段に変更→配列の再ソートと実装すると、割引適用するたびにソートが入り、結果としてTLEになってしまいます。
正しい解法
今回の様に、毎回ソートすることができない。でも最大値を更新して、その値を取得したい。といった場合には、優先度付きキューを使用します。優先度付きキューについては下記を参照してください。
今回は、この優先度付きキューを使用する必要があるという点に気がつけなかったことが敗因でした。ただ、仮に気がついたとしてもC#には標準ライブラリに優先度付きキューがないので、実装する必要があります。なので、今後用に使用するかもしれない処理で割とコード量が多めのものはライブラリとして作成していこうと考え、今回の優先度付きキューから実装をしました。
今回の優先度付きキューはこれを参考に少しだけ修正しました。 github.com
感想
今回のように、こういう処理はこういう方法を使う、という手札をもっと増やすために、過去問をもっと解いていく必要がありますね。
