AtCoder Grand Contest 011 E - Increasing Numbers
公式解説と少し違う方法で解いたので記録しておきます。
解法
十進法の桁を、一番下の桁を 桁目とするように表記します。 桁目は に対応する桁です。
「各桁から を引く回数」の条件への言い換え
非負整数が増加的であることは、「1
を任意個並べたような整数」を9個以下足し合わせたものとして表現できることと同値です。このことからこの問題を以下のように言い換えることができます。
- 与えられた整数 を、「
1
を任意個並べたような整数を引く」という操作をできるだけ少ない回数行って にせよ。その回数が 回であるとき、 が答えとなる。
これをさらに、各桁から が引かれた合計回数に注目して言い換えます。「1
を任意個並べたような整数を引く」という操作 回によって 桁目から が引かれた合計回数を とすると、 かつ数列 は広義単調減少となります。逆にこのような数列には必ず対応する操作列が存在します。
よってこの数列を、 をなるべく小さくするように構成していくことを目指しましょう。
数列の構成方法
方針としては下の桁から見ていきます。 桁目を見るときには
- が広義単調減少になっている
- 桁目までの操作によって、 の 桁目が全て になっている
ようにしながら、 をなるべく小さく保ちます。そして後の桁で単調減少性を保てなくなったら、見終わった桁を最小限のところまで遡って回数を増やし、単調減少性を保つようにします。
の 桁目の値を と書くことにします。具体的に 桁目から を引く回数 を決めるときには、以下のようにすれば良いです。
の場合
このときは単に とすれば、単調減少性を保ちながら 桁目を にできます。
の場合
こっちが問題です。このまま とすると単調減少性が壊れるので、今までの桁を遡る必要があります。このとき である( ではない)ことに注意しておきます。
まず を増やします。既に の 桁目は になっているので、これを保ったまま を増やすとなると最小で 増やすことになります。新しく 桁目から 回引くことにしたので、 は 減ります。
この操作は連鎖する可能性があります。もしこの 増やした操作によって となってしまったら、 も 増やさないといけません。新しく 桁目から 回引くことにしたので、そのぶん は 減らします。
これを単調減少性が保たれるまで繰り返します。つまり 桁目まで遡ることになるか、元々 であるような 桁目で止まります。
この一連の処理は以下のようにまとめることができます。
- であって であるような最大の を求める。存在しない場合は とする。
- に を加算する。
- に を加算する。
- とする。
であることから、この一連の処理によって が負になることや になることはありません。
この処理に必要なものは、まずは区間加算・一点取得のデータ構造です。遅延セグ木でも良いですし、BITをimos法の要領で使ってもできます。次に となるような を管理する必要がありますが、1回の処理で「 であるかどうか」が変化し得るような箇所は定数個なので、操作のたびにそれらを調べて std::set
等に入れておけば最大値を取り出せます。
これを最上位桁まで続けて、最後の時点での が答えになります。