GCJ2015 Round1C C.Less Money, More Problems

問題

D種類の異なる金額を表すコインがある。
各種、C枚までしか使うことができない。
1〜Vまでの金額をすべて払えるようにしたい。
あと最低何種類追加すればすべて払えるようにできるか？

T<=100
Small C=1, 1<=D<=5, 1<=V<=30
Large 1<=C<=100, 1<=D<=100, 1<=V<=10^9

考え方

全探索(small)

与えられたD種コインで作ることができない最低の金額をeとする。
eを作ることができるようにするために、1以上e以下のまだ持っていないコインを追加してあげる必要がある。
追加するコインの最小数を再帰的に全探索すればよい。

greedy解(small)

例えば、コイン1,2,3を持っていている場合を考える。
これで作ることができる金額は、1,2,3,4,5,6なので、Vが7以上の場合は、上記の全探索では4,5,6,7を確認するやり方をしている。
しかし、4を追加すれば10まで、5を追加すれば11まで、6を追加すれば12まで、7を追加すれば13まで、のように、7を追加した方がより多くの数を作ることができるので、作ることができない最低の金額がeの場合は、eをコインとして追加するのが最適になる。

これを繰り返して作ることができない最低金額eがVより大きくなるまで繰り返せばよい。
smallの場合は、Vが小さいので、eを求めるのに、今あるコインで作ることができる金額を全部生成しても間に合う。(簡単なdp？)

greedy解(large)

smallのgreedy解をC>1で考えても、同様に考えることができる。
ただ、Vが大きいので、作ることができない最低金額eを高速に求められるようにする必要がある。

そこで、ひとつ前の作ることができない最低金額がe'だった場合を考える。
コインe'を追加したことで、「e'*C+(e'未満のコインの合計)*C」までは作ることができるのがわかる。
しかし、さらに、「e'*C+(e'未満のコインの合計)*C」未満のコインも使うことでさらに多くの金額が作ることができることがわかる。

そこで、eを更新するのではなく、「0〜xまではすべて作ることができる」というxを更新していくことを考える。
このとき、x+1以下の持っているコインで作れる金額の合計がxならば、作ることができない最低金額はx+1になる。
もし、合計がV以上になっているなら終了、合計がx+1以上になるのであればxをその合計値に更新する、ということを繰り返せば、eを効率的に求めながら計算できる。