解の構成方法の一例を示します。

\(L = \sum_{i=1}^{n}{A_i\times C_i}\)（払える最大の金額）とします。

いったん、支払いに使った硬貨がおつりとして返ってきてはいけないという条件を無視して考えます。 そうすると、持っている硬貨をすべて使って、\(L-M\) 円のおつりを受け取ることで、最小の枚数を達成できます。

このとき、おつりとして受け取る各硬貨の枚数を \(R_1, R_2, \dots, R_N\) とします。

実は各硬貨を

\[ \max(A_1-R_1, 0), \max(A_2-R_2, 0), \dots , \max(A_N-R_N, 0) \]

と支払うことで、条件を満たしつつ、手元に残る硬貨の枚数を \(R_1, R_2, \dots, R_N\) とすることができます。

証明

\(L = \sum_{i=1}^{n}{A_i\times C_i},\, L-M = \sum_{i=1}^{n}{R_i\times C_i}\) より、\(M\) は以下のように表せます。

\[ M = \sum_{i=1}^{n}{(A_i-R_i)\times C_i}. \]

また、支払う総額が \(\sum_{i=1}^{n}{\max(A_i-R_i, 0)\times C_i}\) 円であることから、おつりの総額を \(X\) 円とすると、\(X\) は以下のように表せます。

\[ X = \sum_{i=1}^{n}{\max(A_i-R_i, 0)\times C_i} - M. \]

これを、\(M = \sum_{i=1}^{n}{(A_i-R_i)\times C_i}\) を用いて変形すると以下のようになります、

\[ X = \sum_{i=1}^{n}{\max(A_i-R_i, 0)\times C_i} - \sum_{i=1}^{n}{(A_i-R_i)\times C_i} = \sum_{i=1}^{n}{\max(R_i-A_i, 0)\times C_i}. \]

ここで、\(\max(R_i-A_i, 0)\le R_i\) より、この式から、硬貨 \(i\) の枚数を \(\max(R_i-A_i, 0)\) とする支払い方が、\(X\) 円の支払い方で最小の枚数を達成することが言えます。 （そうでないと \(R_1, R_2, \cdots, R_N\) が \(L-M\) 円の支払い方で最小の枚数を達成することに反します。）

つまり、おつりは硬貨 \(i\) が \(\max(R_i-A_i, 0)\) 枚返ってきます。 このとき、おつりとして返ってくる硬貨を支払いに使用しないという条件は満たされます。

各硬貨 \(i\) について、手元に残る硬貨の枚数を考えると、

\[ A_i - \max(A_i-R_i, 0) + \max(R_i-A_i, 0) = R_i \]

となり、\(R_i\) 枚であることが示せます。

クレジット

原案： US_cube

解法： US_cube,

問題準備・解説： hirakuuuu

レビュー： mono_1729

テスター： physics0523

校正： nu50218