[Codeforces] Codeforces Round #667 (Div. 3) D. Decrease the Sum of Digits

2020年9月11日

問題

方針

イメージとしては下位の桁の数字を \( 0 \) にしていくためのコストから計算していきます。

自然数 \( n \) の桁和を \( f(n) \) とします。自然数 \( n, s \) が与えられたとき、

\[ f(n + x) \leq s\]

を満たす \( 0 \) 以上の最小の整数 \( x \) を求めます。これは \( n \) の下位の桁から見ていくことで解くことができます。\( n \) の \( i \) 桁目の数字を \( n_i \) とします。このとき、

\[ f(n + 10 – n_1) \leq  f(n)\]

が成り立ちます。これは、\( n + 10 – n_1 \) の \( 1 \) 桁目が \( 0 \) となるからです。同様に \( 2 \) 桁目以降について調べるために、\( n \leftarrow n + 10 – n_1 \) と更新します。また、\( n \) の \( i \) 桁目の数字は、

\[n_i = \left \lfloor \dfrac{n}{10^{i – 1}} \right \rfloor \bmod 10 \]

と計算できるので、\( n \leftarrow n + 10^{i-1}(10 – n_i) \) と更新されます。

コード