AtCoder ABC 101 D - Snuke Numbers (ARC 099 D) (黄色, 500 点)

完全に冷静さを欠いたし、ハマった。。。

ARC 099 D - Snuke Numbers

問題概要 (ARC 099 D / ABC 101 D)

正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) / N < f(M) / M が成立することを言う。

すぬけ数を小さい順に K 個求めよ。

制約

K >= 1
K 番目に小さいすぬけ数は 10¹⁵ 以下

解法: 候補を絞って全探索

とりあえず 1 の位が 9 でないと不味そうなことは直感的にわかる。たとえば

$\frac{499998}{48}$ > $\frac{499999}{49}$

となっているので、499998 は候補から外れてしまう。499998 が 499999 になっても分子の比率としてはほとんど上がらない (1.00002 とか) が、分母は 48 が 49 になるので比率が大きく上がることによっている。分母の比率が大きく上がるので、結局全体として小さくなる構図になっている。

これをふくらませて、後ろが 9 で固まると強そうである。したがって、以下のように「最高位以外は 9」な数しかすぬけ数にならないのではと予想を立てたくなるのだが...

199999
299999
399999
499999
...
999999

コーナーケースとして

1499999

のようなケースがある。

$\frac{1499999}{50} \le \frac{1599999}{51}$

が成り立ってしまう。つまり、1499999 以上の整数の中では一番 N/S(N) が小さくなりそうな相手 (であることは本当は要証明だが...) であるはずの 1599999 よりも N/S(N) が小さくなっているので、1499999 はすぬけ数である。これは、さっきのように 499998 と 499999 といったように 1 の位が 1 増えても、比率でみるとあまり変わらないのに対し、1499999 と 1599999 とでは結構比率が違うことに依っている。つまり、1 の位が 1 増えるのではなく、十分高い位が 1 増えると比率も大きく上がるので、分母の比率 up を追い越してしまう可能性がある。

というわけで、先頭はある程度 9 以外になっていてもよいことがわかる。具体的に実験すると、

4 桁のすぬけ数は 1099, 1199, 1299, ..., 1899, 1999, 2999, 3999, 4999, ...., 8999, 9999
5 桁のすぬけ数は ab999 の形
...

という感じに 11 桁程度までのすぬけ数はすべて、ab9999...9 の形になるようである。しかし 15 桁まで行くと abc9999...9 がすぬけ数になり得る。

先頭がどの程度 9 以外になると必ずダメになるのかを考える。「確実にすぬけ数とはならない範囲」は除外してしまって、探索候補を絞って探索すればよい。"{p}999999" 的なやつがすぬけ数でなくなる条件、すなわち "{p}999999" 的なやつよりも "{p+1}999999" 的なやつの方が小さくなる条件を考える。 $p10^{n}-1$ と、 $(p+1)10^{n} - 1$ とを比べる ( $p$ が 1 ずれる)。 $b = f(p)$ とする。

$\frac{p10^{n} - 1}{b}$ > $\frac{(p + 1)10^{n} - 1}{b + 1}$
⇔ $p10^{n} - 1$ > $b10^{n}$

これはざっくり $p$ > $b$ である。 $b$ は最大でも 9 * 15 = 135 であるから、 $p$ > 135 の場合はすぬけ数とはなり得ない。よって、安全を考慮しても $p \le 150$ まで試せばよい。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long f(long long n) {
  long long res = 0;
  while (n > 0) {
    res += n%10;
    n /= 10;
  }
  return res;
}

double g(long long n) {
  return (double)(n)/f(n);
}

int main() {
  vector<long long> res;
  long long base = 1;

  // まずは候補を (1〜150)99999 的なやつを全列挙
  for (int i = 0; i < 15; ++i) {
    for (int j = 1; j < 150; ++j) {
      res.push_back(base * (j+1) - 1);
    }
    base *= 10;
  }
  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());

  // ダメなやつを除く: O(n^2) かかる効率悪い実装だけどとりあえず
  for (long long i = 0; i < res.size(); ++i) {
    for (long long j = i+1; j < res.size(); ++j) {
      if (g(res[i]) > g(res[j])) {
        res.erase(res.begin() + i--);
        break;
      }
    }
  }

  long long K;
  cin >> K;
  for (long long i = 0; i < K; ++i) {
    cout << res[i] << endl;
  }
}