https://betrue12.hateblo.jp/entry/2020/01/22/215123

公式解説と少し違う方法で解いたので記録しておきます。

解法

十進法の桁を、一番下の桁を $0$ 桁目とするように表記します。 $k$ 桁目は $10^{k}$ に対応する桁です。

「各桁から $1$ を引く回数」の条件への言い換え

非負整数が増加的であることは、「1を任意個並べたような整数」を9個以下足し合わせたものとして表現できることと同値です。このことからこの問題を以下のように言い換えることができます。

与えられた整数 $N$ を、「1 を任意個並べたような整数を引く」という操作をできるだけ少ない回数行って $0$ にせよ。その回数が $T$ 回であるとき、 $\lceil\frac{T}{9}\rceil$ が答えとなる。

これをさらに、各桁から $1$ が引かれた合計回数に注目して言い換えます。「1 を任意個並べたような整数を引く」という操作 $T$ 回によって $k$ 桁目から $1$ が引かれた合計回数を $t_{k}$ とすると、 $t_{0} = T$ かつ数列 $t_{0}, t_{1}, ...$ は広義単調減少となります。逆にこのような数列には必ず対応する操作列が存在します。

よってこの数列を、 $t_{0}$ をなるべく小さくするように構成していくことを目指しましょう。

数列の構成方法

方針としては下の桁から見ていきます。 $k$ 桁目を見るときには

$t_{0}, ..., t_{k}$ が広義単調減少になっている
$k$ 桁目までの操作によって、 $N$ の $0, ..., k$ 桁目が全て $0$ になっている

ようにしながら、 $t_{0}$ をなるべく小さく保ちます。そして後の桁で単調減少性を保てなくなったら、見終わった桁を最小限のところまで遡って回数を増やし、単調減少性を保つようにします。

$N$ の $k$ 桁目の値を $a_{k}$ と書くことにします。具体的に $k$ 桁目から $1$ を引く回数 $t_{k}$ を決めるときには、以下のようにすれば良いです。

$t_{k-1} \ge a_{k}$ の場合

このときは単に $t_{k} = a_{k}$ とすれば、単調減少性を保ちながら $k$ 桁目を $0$ にできます。

$t_{k-1} \lt a_{k}$ の場合

こっちが問題です。このまま $t_{k} = a_{k}$ とすると単調減少性が壊れるので、今までの桁を遡る必要があります。このとき $1 \le a_{k} \le 9$ である（ $0$ ではない）ことに注意しておきます。

まず $t_{k-1}$ を増やします。既に $N$ の $k-1$ 桁目は $0$ になっているので、これを保ったまま $t_{k-1}$ を増やすとなると最小で $10$ 増やすことになります。新しく $k-1$ 桁目から $10$ 回引くことにしたので、 $a_{k}$ は $1$ 減ります。

この操作は連鎖する可能性があります。もしこの $10$ 増やした操作によって $t_{k-2} \lt t_{k-1}$ となってしまったら、 $t_{k-2}$ も $10$ 増やさないといけません。新しく $k-2$ 桁目から $10$ 回引くことにしたので、そのぶん $t_{k-1}$ は $1$ 減らします。

これを単調減少性が保たれるまで繰り返します。つまり $0$ 桁目まで遡ることになるか、元々 $t_{m-1} \ge t_{m} + 10$ であるような $m$ 桁目で止まります。

この一連の処理は以下のようにまとめることができます。

$m \lt k$ であって $t_{m-1} \ge t_{m} + 10$ であるような最大の $m$ を求める。存在しない場合は $m = 0$ とする。
$t_{m}$ に $10$ を加算する。
$t_{m+1}, ..., t_{k-1}$ に $9$ を加算する。
$t_{k} = a_{k}-1$ とする。

$1 \le a_{k} \le 9$ であることから、この一連の処理によって $t_{k}$ が負になることや $t_{k-1} \lt t_{k}$ になることはありません。

この処理に必要なものは、まずは区間加算・一点取得のデータ構造です。遅延セグ木でも良いですし、BITをimos法の要領で使ってもできます。次に $t_{m-1} \ge t_{m} + 10$ となるような $m$ を管理する必要がありますが、1回の処理で「 $t_{m-1} \ge t_{m} + 10$ であるかどうか」が変化し得るような箇所は定数個なので、操作のたびにそれらを調べて std::set 等に入れておけば最大値を取り出せます。

これを最上位桁まで続けて、最後の時点での $\lceil\frac{t_{0}}{9}\rceil$ が答えになります。