AOJ 1603 - 500円玉貯金
500-yen Saving | Aizu Online Judge
提出コード
最終的な目標は、
➀ 500円玉の枚数をできるだけ多くする
➁ ➀の中で、購入額を最小にする
という二つなので、これを評価値として動的計画法を利用します。
動的計画法をする前に、少しだけ考察をします。
あるお土産について、どんな買い方をすれば500円を入手できるのでしょうか。これは、主に2パターンに場合わけできることがわかります。お土産の値段を1000で割ったときのあまりが500を超えているかどうか、です。
1000で割ったときのあまりが500を超えていない場合
例えばお土産の値段が400円であったとします。この時、1000円札1枚を使用して購入すると、おつりが600円となり、500円玉を入手することができます。1000で割ったときのあまりが500を超えている場合
例えばお土産の値段が600円であったとします。この時、1000円札1枚を使用して購入すると、おつりは400円であるため、500円玉は入手できません。この場合は、1100円以上支払うと、おつりが500円以上になり、500円玉を入手できます。
2つめのパターンについて、もう少し詳しく見てみると、500円玉を入手するには、
そのお土産を購入するのに必要な1000円札お土産の値段を500で割ったあまり
を支払う必要があることがわかります。手元にあまりがないとき、500円玉を入手できないこともこれより明らかになります。
以上の考察より、お土産の購入方法を決めるために、お土産の値段を1000で割ったあまりが強く関係していそうである、ということがわかりました。
この2つのパターンは、言い換えると
- お土産を1000円札だけで購入したときに、500円玉が手に入ったかどうか
というように言い換えることができます。
そこで、お土産の値段の入力をする際に、1000円札だけで購入した場合にもらえるおつりもセットで記録しておきます(今回は構造体で保持しました)。
さて、本格的に動的計画法について考えていきます。
最初にも述べたように、今回の評価方法は
➀ 500円玉の枚数の降順
➁ ➀が等しい時、購入額の昇順
となっているので、DP配列は、
500円玉の枚数
現在の購入額
の二つを持つ構造体を型として使用していきます。
また、先ほど少しだけ述べたように、手元にある1000円札以外の硬貨(以後、端数と呼ぶことにします)も、500円玉を入手できるかに大きくかかわってくるので、DP配列をdp[i][j]と置いたときに、
- i番目までの店をまわり終えたときに、端数がjになるような最適解(上記の評価が最大)
となることを目標にします。最終的な答えは、dp[n][j]をすべて探索したときの最適解です。初期化についてですが、i,jが0のときに合計金額を0、それ以外のときにはinfをいれておきます。端数が0であるのと、購入方法が存在しないことを区別するためです。
基本的に500円玉の枚数を増やしていきたいので、500円玉を入手できるような購入方法が一番いいです。なので、
- 1000円札だけで購入してもおつりが500円以上になるパターン
は、確実に購入をすることになります。
このパターンのときに、dp配列のどこを参照すればいいかということを考えてみます。i番目のお店にくる手前(つまりi-1)の時点での、手持ちの端数と、今もらうおつりの端数の和が、ちょうどjになっていなければなりません。よって、
dp[i-1][j-今もらえるおつりの端数]
となります。
その値をひっぱってきて、そこに、500円玉1枚と、購入金額を足すという処理をします。
つまり、jが、今もらえるおつりの端数以上でないと、この処理はできません。
500円玉を増やす手段はもう一つありました。
- 端数を利用して500円玉をつくるパターン
です。こちらは先ほどとは違い、購入後に端数が増えるのではなく減るので、
dp[i-1][j+今のお店で500円玉を入手するために必要な端数]
を参照してあげることになります。ここの配列に、なんかしらの値が入っていなければ、i番目のお店で500円玉を入手することはできません。
今回も、500円玉1枚を増やし、購入金額を足すという処理をします。
ここまでで、動的計画法の処理のうち、500円玉を入手するパターンの処理をまとめ終わりました。
さて、500円玉を入手できないパターンはどうすればいいのでしょうか。
ここも、2つのパターンが存在します。
1000円札だけを利用して端数だけ増やすパターン
そもそも購入しないパターン
です。
1000札だけを利用して端数を増やすパターンは、1000円札のみを払って500円玉が入手できるパターンと参照する場所は同じで、
dp[i-1][j-今もらえるおつりの端数]
です。先ほどと違うのは、処理の中身です。500円玉は増えないので、合計金額だけを増やします。
そもそも購入しないパターンは一番簡単です。
dp[i-1][j]
をそのまま代入するだけで済みます。
DPの配列の処理が4つでてきました。まとめると、
1000円札のみで購入しても500円玉を入手できる場合
dp[i-1][j-入手できる端数]を参照し、500円玉の枚数と購入金額を足す
dp[i][j]の最適解はこれになる。1000円札のみで購入したら500円玉が入手できない場合
➀ 端数を利用して500円玉を入手する
dp[i-1][j+必要な端数]を参照し、500円玉の枚数と購入金額を足す
➁ 1000円札のみで購入し、端数を増やす
dp[i-1][j-入手できる端数]を参照し、購入金額のみ足す
➂ そもそも購入しない
dp[i-1][j]をそのまま代入
➀～➂の中で、評価値が最も高いものをdp[i][j]の最適解とする。
となります。最後に、dp[n][j]をすべて探索して、最適解を見つければ答えになります。
