ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Grand Contest 011 E - Increasing Numbers

E - Increasing Numbers

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

解法

十進法の桁を、一番下の桁を  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 が答えになります。

ACコード

Submission #9658581 - AtCoder Grand Contest 011