ARC099 D. Snuke Numbers
問題
整数nについて、nを十進数で表したときの各桁の和をS(n)とする。
正の整数nで、nより大きいすべての正の整数mに対してn/S(n) <= m/S(m)が成り立つものをすぬけ数と呼ぶ。
整数Kが与えられたとき、すぬけ数を小さい方からK個列挙せよ。
制約
- 1 <= K
- K番目のすぬけ数は10^15以下
解法
「ある整数xについて、それより大きい整数yでy/S(y)が一番小さいものを求める関数f(x)」を考え、順次適用していくことを考える。
f(x)のアルゴリズムを考える。
まず、xより大きいyはx+1以上の整数で、これを全探索するのは無理なので、探索範囲を減らすことを考えたい。
桁数がkの整数yを考えたとき、k桁の整数のうち、S(n)が最大となるのは、999...999のように9がk個ならんだものになる。
桁数がk+1の整数がこの999...999よりn/S(n)が大きくならなければ、「k桁の整数だけ考えればよい」ということがわかる。
例えば、k=3の場合を考えると、999は、S(n)=27なので、k+1=4桁の整数を考えた場合にS(n)が27以上の整数になっていなければ分子は大きくなるのでn/S(n)は小さくならない。
しかし、4桁の整数で、nをあまり大きくせずにS(n)が27以上整数を考えると、
S(n)=27→一番小さい4桁のnは1899
S(n)=28→一番小さい4桁のnは1999
S(n)=29→一番小さい4桁のnは2999
S(n)=30→一番小さい4桁のnは3999
S(n)=31→一番小さい4桁のnは4999
S(n)=32→一番小さい4桁のnは5999
S(n)=33→一番小さい4桁のnは6999
S(n)=34→一番小さい4桁のnは7999
S(n)=35→一番小さい4桁のnは8999
S(n)=36→一番小さい4桁のnは9999
となっており、nの増え方とS(n)の増え方的に、k+1桁以上のn/S(n)はk桁の9が並んだものより大きいn/S(n)になってしまう。
したがって、k桁のものだけを考えればよい。
とはいえ、すぬけ数は10^15まであるので、15桁程度の探索をそのままするのはまだ無理。
f(x)の候補となる整数をさらに候補を絞りたい。
候補となる整数として、y=12534のような整数を考えると、これはまだyより大きいものでy/S(y)を小さくできるものが考えられて、12539のようにちょっと大きくすることで、S(y)を14から19に増やせてy/S(y)を改善できてしまう。
y=12534より大きいものとして、1桁目を大きくする12535,12536,...12539と、2桁目を大きくする1254x,1255x,...,1259x、3桁目を大きくする126xx,127xx,...・・・と考えられる。
xの部分を任意の整数で考えてみると、1254xはxが9じゃない場合は12539の方がS(y)が小さいため、改善しないことがわかる。
同様に考える3桁目4桁目・・・と、xの部分は9じゃないとそれより改善するものが存在してしまうためxの部分は9だけ考えればよい。
したがって、考えるべきは、1桁目を大きくする場合、2桁目を大きくする場合(ただし、1桁目は9)、3桁目を大きくする場合(ただし1桁目と2桁目は9)、・・・という感じで、桁数*10程度の候補がy/S(y)を小さくする可能性があるので、探索すればよい。
1→f(1)→f(f(1))→・・・と繰り返せばよく、f(x)の計算量は、O(xの桁数*10)程度なので、十分高速に求めていける。
(嘘)解法
理論保証がないアプローチだが、実験して探索範囲を減らして解を探す方法でも通ってしまう。
mは∞まであるが、ある程度の数値で打ち切って実験してみると、xxx99999のような感じになっていることが確認できる。
桁数を増やして、上位3～4桁分を任意の数として後ろに9を並べた数字を考えると、すぬけ数の候補と考えられるので、列挙して、実際にそれらの数値だけ比較して条件を満たすものを返す。
