geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC231 Minimal payments

ABC お釣り問題

解説AC

お釣りの問題は過去出題例があります。

過去問では、

を参考にしました。

この解説と公式解説を踏まえ、まずは解法を書きます。

例として、

X = 35

A = {1,4,12}

を考えます。

$f(x)$ を $x$ 円払うために必要な最小の硬貨の枚数

と定義します。

$35\ mod\ 4=3$ は、1円玉でしかやり取りできません。

・1円硬貨で3円払って32円払う問題とする

・1円硬貨を使わず、おつりとして1円を受け取ることを確定させ、36円を払う問題とする

ことができます。

よって、35円を払うのに必要な最小枚数 $f(35)$ は、

$f(35)=min(f(32)+\frac{35-32}{1},\ f(36)+\frac{36-35}{1})$

となります。

同様に、 $f(32),f(36)$ は以下のように計算できます。

$f(32)=min(f(0)+\frac{32-0}{4},\ f(36)+\frac{36-32}{4})$

$f(36)=min(f(0)+\frac{36-0}{4},\ f(36)+\frac{36-36}{4})$

そして、 $f(0)=\frac{0}{12},f(36)=\frac{36}{12}$ というように計算できます。

各硬貨を考慮したときには、

・X以下の最小の $A_i$ の倍数。(ここでは $S_i$ とします。)

・X以上の最大の $A_i$ の倍数。(ここでは $T_i$ とします。)

の2パターンしか現れません。

そこで、以下のDPを考えます。

$dp[i][j]:=$

j=0のとき、 $S_i$ 円払うのに必要な硬貨の最小枚数
j=1のとき、 $T_i$ 円払うのに必要な硬貨の最小枚数

初期値は、

$dp[N][0] = 0,\ dp[N][1]=\frac{T_i}{A_i}$
です。

漸化式は、

$dp[i][0]\leftarrow min(dp[i+1][0]+\frac{S_i - S_{i+1}}{A_i},\ dp[i+1][1]+\frac{T_{i+1}-S_i}{A_i})$

$dp[i][1]\leftarrow min(dp[i+1][0]+\frac{T_i - S_{i+1}}{A_i},\ dp[i+1][1]+\frac{T_{i+1}-T_i}{A_i})$

これを金額が大きい順に計算しておくと、答えは $dp[1][1]$ (または $dp[1][0]$ 。等しくなるはず)です。

「 $A_{i+1}$ は $A_i$ の倍数である」がよくわからなかったこともあり、数直線で考えてみました。

下記の表は $A_i$ の倍数でいける座標( $A_i$ 円硬貨で払える金額)を示したものです。

f:id:geam1113:20211230065338j:plain

表を見ると分かるように、 $A_{i+1}はA_i$ の倍数であるという制約により、4円硬貨で支払えない金額は、12円硬貨でも払えません。

したがって、

・ $X\ mod\ A_i$ で得られる端数は、 $A_{i-1}$ 円以下の硬貨で支払うしかない

ことが言えます。

また、

・DPの過程で、 $A_i$ 円硬貨で支払う金額、 $S_i - S_{i+1}$ 、 $T_{i+1}-S_i$ 、 $T_i - S_{i+1}$ 、 $T_{i+1}-T_i$ が、 $A_i$ の倍数である

ことが保証されます。

この問題は、以下のように数直線上を移動する問題に言い換えができそうです。

0から始まり正の方向に無限に伸びる数直線があり、その数直線上を点0から点Xまで移動することを考える。

$A_1,\cdots ,\ A_N$ だけ、進むか戻ることができるとき、操作回数は最小で何回か。

数直線上を移動する問題においても、

・値の大きい方から移動した方が効率が良い

・Xに最も近い $A_i$ の倍数、すなわち $S_i$ または $T_i$ のみに移動すればよく、他は無駄である

・考慮する移動方法は、

　　・ $S_{i+1}$ から $S_i$ または $T_i$ に行く

　　・ $T_{i+1}$ から $S_i$ または $T_i$ に行く

ことから、元の問題と同様に解けるかなと思います。

提出コード