ARC099 D : Snuke Numbers(500)
作成日：2018.10.03
最終更新日：2018.10.03
問題概要
正の整数$n$を十進法で表した時の各桁の和を$S(n)$とする。
正の整数$n$で条件「任意の整数$m$に対して$n \lt m$ならば$\frac{n}{S(n)} \leq \frac{m}{S(m)}$」を満たすものを小さい方から$K$個列挙せよ。
制約
$1 \leq K$
$K$番目に条件を満たす整数は$10^{15}$以下
考え方
ある桁が$1$大きくなった時を考えると、正整数$n$が条件を満たすには$\frac{n}{S(n)} \leq \frac{n+10^k}{S(n)+1}$であることが必要である。
この必要条件は$n \leq S(n) 10^k$と変形できる。
一方$n \leq 10^{15}$の時$S(n) \leq 9 \times 15$$= 135$であるから、$n \geq 10^{k+3}$である時はこの必要条件が成り立たない。
すなわち$n$の上$3$桁を除いた桁はすべて$9$である必要がある。
上$3$桁以外の桁がすべて$9$である$10^{15}$以下の正整数は$99 + 900 \times 13$$= 11799$個であるから、これらすべてに対してのみ条件を満たしているかを確認すれば良い。
後は$10^{15}-1$が条件を満たすことを確かめれば良い。
これは$1$桁増えても$S(n)$が高々$16/15$倍にしかならない上、$\frac{16}{15} \times 10^{15}$以下の$16$桁の整数では$S(n)$が$135$未満となることから分かる。
$S(n)$を求めるのは$O(log \: n)$ででき、候補となる整数それぞれにおいて条件を確かめられる回数はならしで$O(1)$であるから、これで十分高速に列挙できる。
ソースコード
マクロ等はこちら
vector<LL> ans;
LL S(LL x){
LL ret = 0;
for(; x ; x /= 10) ret += x%10;
return ret;
}
void check(LL x){
LL y = S(x);
while(ans.size()){
LL p = *ans.rbegin();
if(p*y > x*S(p)) ans.pop_back();
else break;
}
ans.push_back(x);
}
int main(){
int K; cin >> K;
repp(i,1,100) check(i);
LL a = 0 , b = 1;
while(a < 1e12){
repp(i,100,1000) check(i*b+a);
a = a*10+9;
b *= 10;
}
repp(i,0,K) cout << ans[i] << endl;
return 0;
}解法まとめ
上$3$桁以外の桁がすべて$9$である$10^{15}$以下の正整数のみを考える。
条件を満たす整数のうち小さいものから$K$個を列挙すれば良い。(21-28行)
条件の確認は、新たな候補$x$が増えるたびに、これまでに残っている整数のうち大きいもの($p$とする)から順に$\frac{p}{S(p)} \gt \frac{x}{S(x)}$を満たさなくなるまで削除することで行える。(9-17行)