ABC 161 D Lunlun Number
以下の条件を満たす正の整数$ Xをルンルン数と呼ぶ。小さい方から$ K番目のルンルン数は何か?
$ X を十進数表記した際に、隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下
制約: $ 1 \leq K \leq 10^5
---
小さい方から$ K番目と聞くと、
ある数$ N以下の条件を満たすものの個数を数え、それが$ K個以下かそうでないかによって二分探索し、最終的に得られた$ Nが$ K番目の値
というアプローチが浮かぶ。今回の場合は桁 DP と組み合わせれば可能。
しかし、解説のような以下のアプローチがシンプルで強力。 初期値群から全ての値を生成することができて、かつそこに「最小の値から生成される値は、その値より大きく、それ以外の値から生成される値より小さい」というルールがあれば、以下のようにして$ K番目の値が得られる
queue に初期値を入れておく
「値を取り出し、その値から生成される値を queue に追加」を $ K回繰り返す
今回の場合、一桁の数$ 1, 2, .., 9を queue に入れておき、末尾に数字を付け加えていくことを考えれば、上記のルールが満たされることがわかる
ここで、 queue でなく priority_queue を使えば、上記の条件が「ある値から生成される値は、その値よりも大きい」という形に緩まり、より汎用的な方法となる。
---
ということで上記のアプローチは頭にとどめておきたいところだが、自分は複雑なアプローチをまず考えてしまった。同じ方法の解説が見当たらないので記しておく。
$ dp [num][digit] :num から始まる digit 桁のルンルン数の個数(0 から始まるものも含む)
を簡単に求めることができることがわかるから、まず求めてしまう。
上記を用いると、ある桁数のルンルン数の個数も求まる。小さい桁から順にルンルン数の総数を数えていき、総数が$ K以上となる桁で止める。それが求めるルンルン数の桁数となる。
桁数が確定したので、今度は各桁の値を決めていく。その桁数未満の数の個数を$ nとすると、この桁数で$ K-n番目の数が求めるものとなる。
個数を数えつつ、先頭の桁から順に$ 1, 2, .., 9を試していく。すなわち、$ dpで求めた「その桁にその数字を入れた場合の残りの桁の通り」と今までの個数の和が$ K-n未満である限り個数に加算し値をインクリメントしていく。
DP を求める過程がボトルネックで、10 通りの数字 * 3 通りの遷移 * 最大桁数(今回はたかだか 10 であることがサンプルからわかる)より $ O(10 * 3 * max\_digit)。