ABC085のC問題を解きました

こんにちは。今日もブログを見てくれてありがとうございます。

今回解いた問題はAtCoder Beginner Contest 085のC問題「Otoshidama」です。

久しぶりに競プロの問題を解きました。

使用言語はRubyです。以前はC++で書いていましたが、最近はRubyに触れることが多く、Rubyの練習も兼ねてRubyで書いてみました。

こちらが私のコードです。Ruby読めないよーって人はごめんなさい。この後する方針の話はRubyやってなくてもわかるように書いていこうと思います。

基本方針は貪欲法みたいな感じで、想定解の全探索もどき二重ループとは違います。

まずは、L9-L20で金額に合わせて出来るだけお札の枚数が少なくなるようにお札を詰めます。この時点で詰め切れない時に解は存在しないのでL21-L25で解無しを出力するようにしています。この後の書き方によってはこの処理は出力の直前に持ってこないと予期せぬ動作が起こるかも。

次に、L26で不足しているお札の枚数（＝使うべきお札の枚数と最小のお札の枚数の差）を記録します。この数値が0になるようにお札を選べば良いというわけです。

L27-L60のループでは、不足しているお札の枚数に応じて一万円札->五千円札*2か五千円札->千円札*5の変換（両替みたいな感じのこと）をします。この処理では、それぞれ不足しているお札の枚数を1または4枚減らすことができます。

4枚以上不足していたら五千円札->千円札*5を、不足が4枚以下なら一万円札->五千円札*2をします。これを繰り返すことで不足が0枚になることを目指します。

両替できる一万円札や五千円札がなくなった時点で解無しが確定します。

不足枚数が負の値になったときの処理も書いていますが、ここまでの処理が正しく行われていれば負の値になることはないです。

最後に注意点ですが、whileは条件式がtrueの時に実行を続けます。忘れないでください。

わからない点があったらコメントかTwitterにお願いします。

計算量がNに比例するかとか、同じ方針で高速化できるなどありましたら教えてくれると嬉しいです。

最後まで読んでくれてありがとうございました。