ABC155 E - Payment - あっとのTECH LOG

問題原文

問題要旨

$10^{0}, 10^{1}, 10^{2} ... 10^{10^{100}}$ の $10^{100} + 1$ 種類の紙幣がある国を考える。
この国で代金として $N$ を支払う時、 $N$ 以上の額を支払うことで、自分が出す紙幣の枚数とお釣りとしてもらう紙幣の合計枚数を最小化せよ。

$1 \leq N \leq 10^{100000}$

解法

ある桁の払い方を考えると、「その必要枚数ピッタリ払う」か「その桁では１枚も出さずに、上の桁のどこかで多く払う」の２種類があることがわかる。
あとはこの考え方を元に桁dpをすればよい。

ポイントは、「上の桁のどこかで１多く払っているなら、そこからはお釣りだけを考えばよい」ということと、「どこからでも１多く払う部分に遷移ができる」ということ、それと「代金以上払っていることが確定していても、どこかの桁でピッタリ追加で払ってもよい」ということ。

実装

簡素ォ！ $N$ を整数で受け取ると死ぬので気を付けようね（自戒）

N = input()
X = list(map(int, list(str(N))))

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := ピッタリ払う
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := その桁については払わない。上の桁のどこかで１多く払う。
dp1[0] = 0

for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))

感想

前はdpよくわかんなくて、貪欲で詰めようとして。。。となって結果解ききらなかったのだけど、JOI難易度６をやってDP力を鍛えたら瞬殺できた。
ありがとうJOI。。。