AtCoder Beginner Contest 155 E - Payment

上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。

解法

上の桁から見ていって、その桁までで支払う＆お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。

例えば $N = 365$ 円だったとして、 $10$ の位の桁までの硬貨の支払い＆お釣りを処理し終わったとします。このとき支払っている合計金額としては、

$360$ 円。つまり、見ている桁のぴったりまで支払っている。
$370$ 円。つまり、見ている桁の硬貨1枚分だけ多く支払い、それより下の桁でお釣りをもらう。

などが考えられます。そして実は、この2通り以外は考える必要がありません。

もし金額不足、つまり例えば $350$ 円しか払っていないとしましょう。このときは不足分を大量の $1$ 円玉で支払わないといけないので、 $10$ 円玉で払うより明らかに損です。

同様にもし2枚分以上多く支払う、つまり例えば $380$ 円払っていたとします。このときも大量の $1$ 円玉でお釣りをもらう羽目になるので、 $10$ 円玉を払う枚数を減らすべきです。また例えば $100$ 円玉 $4$ 枚で $400$ 円を払っていたとしても、 $10$ 円玉としてお釣りをもらっておくほうが得です。

このように、各桁を見終わった時の支払い金額は「その桁までぴったり」か「1枚分だけ多い」かに限定されます。そのため、この2つを状態として持つようなDPを考えることができます。

$N$ は大きいので文字列として扱い、最上位の桁を $i$ 桁目として書きます。ここで最初に $N$ の先頭に $0$ を付けておくと扱いが楽になります。例えば $N = 999$ 円であるときは $1000$ 円玉（？）を払うのが最適であるように、与えられた $N$ の最上位桁より1つ上の硬貨までは使う可能性があるからです。

DPの状態を以下のように考えます。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 上から $i-1$ 桁目までの硬貨の支払いとお釣りを処理し終わって、 $N$ の $i-1$ 桁目までの金額よりも $j$ 枚分多く支払っているときの、これまでの支払い・お釣り硬貨の最小合計枚数

$dp\lbrack i \rbrack\lbrack j \rbrack$ から $dp\lbrack i+1 \rbrack\lbrack j \rbrack$ までの遷移を4通り考えましょう。 $N$ の $i$ 桁目の数を $A_{i}$ と表記します。

$j=0$ から $j=0$ への遷移：お釣り発生はなく、単に $i$ 桁目の硬貨を $A_{i}$ 払うので、 $A_{i}$ が加算される。
$j=0$ から $j=1$ への遷移：お釣り発生はなく、 $i$ 桁目の硬貨を余分に払うので、 $A_{i}+1$ が加算される。
$j=1$ から $j=0$ への遷移：お釣りが発生する。 $i$ 桁目の硬貨をお釣りとして $10-A_{i}$ 枚受け取るので、 $10-A_{i}$ が加算される。
$j=1$ から $j=1$ への遷移：お釣りが発生する。 $i$ 桁目の硬貨をお釣りとして $10-A_{i}$ 枚受け取るが、そのうち1枚は余分に払う用に返す。そのため $9-A_{i}$ が加算される。

このDPを行い、最後の桁まで見終わったときの「その桁までぴったり支払った」最小合計枚数が答えになります。

他にも色々解法はあるようですが、本記事の解法も含めて多くの解法は「こういう状態は絶対に損」「なのでこういう状態や遷移だけを考えれば十分」という考察が少なからず必要になり、その考察が正しいかに全てが掛かっています。例えば「同じ硬貨を $10$ 枚以上払ったりお釣りとして受け取るのは絶対に損」という知見だけを使って各硬貨を $0, ..., 9$ 枚払う遷移を全て試すDPなんかも堅実で良さそうですが、実行制限時間が厳しいかもしれません…。