ABC 155 E - Payment
問題
$1, 10, \ldots, 10 ^ {1000000}$ 円札で $n$ 円払うとき、渡す枚数とお釣りで使う枚数の和の最小値を求めよ。（$n \leq 10 ^ {1000000}$）
解説
$n$ 円払うときに使われる枚数の最小値を $f(n)$ とすると、$f(0)=0, f(1)=1$ である。 $10n + k$ 円払うときは、$10n$ 円を最適に払ってさらに $k$ 円払うか、$10(n + 1)$ 円払って $10 - k$ 円お釣りもらうかの $2$ 通りのうち少ない枚数になる方を選ぶ。 $f(10n)=f(n)$ であるから、 $$ f(10n + k) = \mathrm{min} \{ f(n) + k, f(n + 1) + 10 - k \} $$
実装
上の式を再帰でそのまま実装すると計算量が大きすぎるので、$n$ の各桁を上から見ていって、その時点でぴったり払う場合の枚数と $1$ 多く払う場合の枚数をそれぞれ $a$, $b$ として、各桁 $i$ について $$ \begin{aligned} a & \leftarrow \mathrm{min} \{ a + i, b + 10 - i \} \\ b & \leftarrow \mathrm{min} \{ a + (i + 1), b + 10 - (i + 1) \} \end{aligned} $$ とすればよい。
n = [int(i) for i in list(input())] a, b = 0, 1 for i in n: a, b = min(a+i, b+10-i), min(a+(i+1), b+10-(i+1)) print(a)
類題
いわゆる桁DPの問題。
