ABC 101 D Snuke Numbers

D - Snuke Numbers

問題概要

正整数nに対して、nを10進法表記したときの各桁の和をS(n)とし、関数gをg(n)=nS(n)と定義する。

そして任意の正整数m>nに対してg(n)≤g(m)が成立するようなnを「すぬけ数」と呼ぶことにする。

このとき、すぬけ数を小さい方から順にK個出力せよ。

K≥1
K番目のすぬけ数は10の15乗以下である。

感想

19,29,39...199,299..みたいに右側が99..となる集合なのかなと思った。その通りに実装したら..なんとTLE。実力不足。
また、右側が99..となる集合でもないらしい。難しい..

WAコード

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


int diget(int num) {

	string str = to_string(num);
	int num1 = str.length();
	if (num1 == 1) return true;

	for (int i = 1; i < num1; i++) {
		if (str[i] - '0' != 9) {
			return false;
		}
	}

	return true;
}

int main() {

	int K = 0; cin >> K;

	int count = 0;
	int i = 1;
	while (1) {

		bool can1 = diget(i);

		if (can1) {
			cout << i << endl;
			count++;
		}

		if (count == K) {
			break;
		}
		i++;
	}
}

解説を見る

参考にさせて頂いたサイト
ARC099(ABC101) 解説 - Mister雑記

理解した後の感想

まずこのすぬけ数、プログラムで扱えるものではないらしい。n<10の15乗という条件があって初めて求められるものとなる。
すべてアルゴリズムでゴリ押すのではなく、この時はどうだろう..と検証していくことがこの問題の肝であると考える。

んー..これは流石に実力不足が過ぎるのでこの問題はスルーするのがよさそう