私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「現地で使いやすい両替」（CodeIQ）を参照してください。
日本から海外旅行に行く場合は外貨に両替しますが、海外からの旅行者が日本に来るときは日本円に両替します。
このとき、現時点でのレートに従って両替しますが、使うときに便利なように、紙幣や硬貨を組み合わせます。
できるだけ現地の文化を知りたいので、多くの種類を組み合わせて両替したいところです。
今回は米ドルから日本円への両替を考えます。
紙幣や硬貨の種類の数が最大になるもののうち、全体の枚数が最小になる両替方法を求め、その全体の枚数を出力してください。
例えば、1ドル112.54円のときに100ドルを日本円に交換すると11,254円で、その交換方法として以下のような例があります。
紙幣・硬貨 例1 例2 例3 例4 例5 1万円札 1 0 0 0 0 5千円札 0 1 1 1 1 2千円札 0 0 1 2 2 千円札 1 5 3 1 1 500円玉 0 2 2 1 2 100円玉 2 1 1 4 1 50円玉 1 2 1 4 2 10円玉 0 5 9 14 4 5円玉 0 0 2 2 2 1円玉 4 4 4 4 4 枚数 9 20 24 33 19
例1は紙幣や硬貨の種類が5種類、例2は7種類なのに対し、例3～5は9種類のため、例3～5の中から、全体の枚数が少ない例5を選びます。
（他のパターンの中でも、例5が最小になります。）
標準入力から両替後の日本円の金額が指定されたとき、紙幣・効果の種類が最大で全体の枚数が最小になる場合を求め、その時の枚数を標準出力に出力してください。
なお、入力されるのは整数のみで、最大でも50,000とします。
【入出力サンプル】
標準入力
11254
標準出力
19
Rubyで解答しています。
#!/usr/bin/ruby
Money = [1,5,10,50,100,500,1000,5000,10000] # 2000は別に扱う
# 2000円以外を両替する
def change(arr,i)
ret = []
x = Money[i] / Money[i-1]
a1 = arr[i-1] % x
b1 = arr[i-1] / x
nxt1 = arr.dup
nxt1[i-1] = a1
nxt1[i] = b1
ret << nxt1
# 大きな貨幣に交換できなかったら終わり
if b1 == 0 then return ret end
# 大きな貨幣に交換した時あまりがなくなるなら強制的に小さい貨幣を作る
if a1 == 0 then
b2 = b1-1
a2 = x
nxt2 = arr.dup
nxt2[i-1] = a2
nxt2[i] = b2
ret << nxt2
end
return ret
end
# 2000円を作る
def change2k(arr)
ret = [arr]
# 1000円が2枚以上ある
if arr[6] >= 2 then
nxt = arr.dup
if (arr[6] == 2) || (arr[6] % 2 > 0) then
nxt[6] = arr[6]%2
nxt[9] = arr[6]/2
else
nxt[6] = 2
nxt[9] = (arr[6]-2)/2
end
ret << nxt
end
# 5000円が1枚以上ある
if arr[7] >= 1
nxt = arr.dup
nxt[7] = arr[7] - 1
nxt[9] = 2
nxt[6] = arr[6] + 1
ret << nxt
end
# 10000円が1枚以上ある
if arr[8] >= 1
nxt = arr.dup
nxt[8] = arr[8] - 1
nxt[7] = arr[7] + 1
nxt[9] = 2
nxt[6] = arr[6] + 1
ret << nxt
end
return ret
end
# 結果を求める
def getResult(cand)
mx = 0
counts = {}
for arr in cand
c = 10 - arr.count(0)
if c > mx then mx = c end
if counts[c] == nil then counts[c] = [arr]
else counts[c] << arr
end
end
ret = 50001
for arr in counts[mx]
s = arr.reduce(:+)
if s < ret then ret = s end
end
return ret
end
# 問題を解く
def solve(n)
base = [n,0,0,0,0,0,0,0,0,0] # 1,5,10,50,100,500,1000,5000,10000,2000
cand = [base]
for i in 1...Money.size
ncand = []
for arr in cand
ncand += change(arr,i)
end
cand = ncand
end
ncand = []
for arr in cand
ncand += change2k(arr)
end
cand = ncand
return getResult(cand)
end
# main
while line = gets
line.strip!
if line.empty? then next end
p solve(line.to_i)
end
昔、同じような両替の問題をやった気がします。
この問題は種類が多い方が優先するという条件がありますが、2000円札がこの部分に関連して面倒です。
小さい方の貨幣から順に枚数が最小になるように確定してゆくというのが基本的な考え方になります。単に枚数を最小にするなら大きな額の貨幣から確定した方が楽ですが、種類が多い方を優先するという条件があるので小さい額の貨幣から確定した方が少し楽と思います。
やり方は、次のようになります。
まず、5円と1円にする場合、入力値を5で割った商を5円の枚数、余りを1円の枚数にします。5円を5円と10円にする場合は5円の枚数を2（=10/5）で割った商が10円の枚数、余りが5円の枚数になります。これを繰り返せば最小の枚数にできます。
種類が多い方を優先するので余りが0になった場合のことを考慮しなければなりません。
これを満たすために、余りが0になった場合、大きな額の貨幣の枚数を1減らし、代わりに小さな額の貨幣を同額になるようにします。この新たに作ったパターンは候補として記録し、同様に高額な貨幣に両替するときの候補とします。
基本的にはこれでできるのですが2000円の扱いが面倒です。
例えば1000円が10枚の時点で2000円を4枚と1000円2枚のパターンを作るのですが、その次の5000円を考えたとき2000円×4は1000円×1、2000円×1、5000円×1と1000円のことを考慮しなければいけません。その上、最適解は前の段階で用意した1000円×2を2000円にして1000円×1、2000円×2、5000円×1にしなければなりません。
私はこれが面倒なので2000円のことを考えずにパターンを作った後、5000円と10000円を崩して2000円を含むパターンを作るという2段階の処理にしました。
入力値を数値にしてsolve()に渡し、結果を印字します。
問題を解きます。
baseは最初の貨幣の枚数で[1円,5円,10円,50円,100円,500円,1000円,5000円,10000円,2000円]という配列になっています。
candはパターンの候補のリストで最初はbaseだけが入っています。
99行目から105行目のループで2000円以外の貨幣に両替した場合のパターンを作ります。定数Moneyは両替する貨幣の単位で[1,5,10,50,100,500,1000,5000,10000]と2000円以外になっています。関数change()は1段階高額の貨幣に両替した場合のパターンのリストを返すのでそれを候補に追加し10000円まで繰り返します。
108〜110行目の処理で2000円を含まないパターンから2000円を含むパターンを作成します。
getResult()で仕様の条件に当てはまるパターンを探し、枚数を求めてそれを返却します。
2000円以外への両替を処理します。
arrは現在のパターン、iは次に両替対象となる貨幣の単位です。
変数retは両替後のパターンのリストを保持する領域です。
xはiが示す貨幣とi-1の貨幣が何倍の金額になるかを表します。
まず、最小枚数になるように両替する処理が10〜15行目になります。
arr[i-1]が現在両替済みの最も高額な貨幣の枚数なのでこれをxで割ったものが枚数が最小になるようにした場合の両替後の枚数、余りがその残りです。これをパターンの1つとしてretに追加します。
もし大きな貨幣に両替できなかったら終了します。
また、余りが0の場合は強制的に1段階小さな貨幣を残したパターンを作らなければならないのでその処理を21〜28行目までで行います。
これは最小枚数にした場合の両替後の最高額の貨幣の枚数を1減らし、代わりに1段階小学の貨幣の枚数を増やすということで行います。これもパターンとして追加します。
最終的にretに両替後のパターンが含まれているのでそれを返却します。
2000円を考慮していないパターンから2000円を含むパターンを作ります。
2000円を作るには次の3通りがあります。
・1000円が2枚以上ある場合、1000円を2000円に変える。
・5000円がある場合、5000円1枚を2000円×2、1000円×1に変える。
・10000円がある場合、10000円1枚を5000円×1、2000円×2、1000円×1に変える。
この3通りの処理を行ってパターンを作り、パターンのリストを返却します。
引数candは候補のパターンのリストです。
この中から貨幣の種類が最も多く、その中で枚数が最も少ないものを選びます。
77〜83行目の処理でそれぞれのパターンが何種類の貨幣を使っているかによって分類します。countsはキーが貨幣の種類、値がその種類の貨幣を使用しているパターンのリストになります。mxは使用した貨幣の種類の最大値です。
85〜89までの処理で最も多くの種類の貨幣を使用したパターンから全体の枚数が最小になるものを探します。
retに最小枚数が記録されるのでそれを返却します。
私は2000円を別扱いしましたが、2000円も同じように扱ううまい方法があったのかなぁ、と少し気になります。大きな額の貨幣から扱えばできそうな気もしますが、小さい額の貨幣を強制的に作る処理が面倒になるので2000円を別扱いするのがやはり単純な気がしますが。
それはそうと、2000円札は全然見かけなくなりました。発行されてから2〜3年しか見かけていないような気がします。