No.288

ゆきうさぎさんの手持ちのお金を $B$ 円とすると, 手持ちのお金を一旦すべて貯金箱さんに預け, その後 $C = B - M$ 円を最小の枚数の硬貨で返してもらえばいい. よって, $C$ 円を $A_1, A_2, \dots, A_N$ 円玉で作る最小の枚数を求める問題となる. (もちろん $C < 0$ なら不可能)

あとは No.31 と似た問題となる.

$C$ がかなり大きくなるので, 通常のナップザック問題のように動的計画法で解くと時間計算量 $O(MN)$ となって間に合わない. そこで, 一番額面が大きい $A_N$ 円玉をなるべく多く使うようにする.

$A_i$ 円玉 ($i \neq N$) を合わせて $A_N$ 枚使ったとして, その $j$ 枚目が $B_j$ 円玉だとする. そして,

$$P_t = B_1 + B_2 + \dots + B_t \ (t = 0, 1, \dots, A_N) \\ Q_t = P_t \ mod \ A_N$$

とおくと, $Q_t$ は $A_N + 1$ 個あるので, 鳩の巣原理により, $Q_u = Q_v$ となる $u, v$ が存在する.

そのような $u, v$ に対して $Q_v - Q_u \ mod \ A_N = 0$ であるので $P_v - P_u = B_{u+1} + B_{u+2} + \dots + B_v$ は $A_N$ で割り切れる. よってこの硬貨の集合をより少ない枚数の $A_N$ 円玉に置き換えることができ, これを繰り返し適用することにより, $A_i$ 円玉の合計枚数は $A_N$ 枚より少なくできる.

すなわち, $C$ 円から $A_N^2$ 円以上を残してできるだけ $A_N$ 円玉で支払うのが最も枚数を少なくできる.

あとは $i$ 番目まで見たときに $j$ 円を支払う最小の枚数を $C(i, j)$ とすると,

$$C(i, j) = \min(C(i-1, j), C(i, j-A_i) + 1)$$

となるので, これを DP で計算すればいい.