ABC101 D - Snuke Numbers

ずっと放置してたABC101-D - Snuke Numbersを解きました.
D - Snuke Numbers

K番目のすぬけ数は$10^{15}$以下とありますが, $1$から$10^{15}$まで調べていると時間が足りないので, 解の候補を絞ってから解を探索する必要があります. 絞り方として, 末尾に9が詰まっている方が有利であることは明らかなのですが, 数値の先頭の方で9でない数字が何桁まで許されるのかは自明ではありません. 例えば, [199,299,399,499,599,699,799,899,999]はすべてすぬけ数で, これだけを見ると上ひと桁のみ変えて残りに9を詰めればよいと思ってしまいますが, [32999 , 339999]もすぬけ数で, この2数のあいだにすぬけ数は存在しません. とりあえずプログラムでは4桁まで変更することにしておいて$10^{15}$までのすぬけ数の数カウントしておき, 3桁までの変更したときのすぬけ数の数と比較すると等しかったので, $10^{15}$までのすぬけ数では3桁までの変更で十分であることがわかりました. そのコードを提出しました. 解候補を選定するときは, $10^{15}-1$が自明なすぬけ数となります. そのS/digit(S)を計算してminとして保持しておき, トップダウン式に候補ごとにS/digit(S)を計算してminを下回ったらminを更新してすぬけ数として採用する, というふうにしました. 制約からS/digit(S)の上界が決まるのでそこからトップダウン式に求めるというのがポイントです.
制約ありきな考察ではありますが, これをボトムアップ式に求めるのは数学な考察が非常に辛い気がします.
Submission #2892148 - AtCoder Beginner Contest 101