AtCoder Regular Contest 099 : D - Snuke Numbers
-
問題
「S(n) := 10 進数表記での n の桁和」としたとき、m > n である任意の正の整数 m に対して n / S(n) <= m / S(m) が成り立つような n を「すぬけ数」と呼ぶとき、「すぬけ数」を小さい方から順に K 個求めよ、という問題。
-
解説
コンテスト中、末尾に何個も 9 が連続するものがよさそうだなあと思う。規則性ぽいものを見つけ出すも、WA。
ここで、あまり難しく考えすぎず ABC999999... の形の数を全列挙してみる。そうすると「すぬけ数」の候補が出てくるのでその中で問題の条件に当てはまるものだけを集めればそれが答えになっている。問題なのはどれだけの大きさの数まで列挙するか、ということ。問題文の制約には「K 番目のすぬけ数は 10^15 以下」とあるので桁数としては 1~16 まで試せばよいと分かる。数の先頭部はどこまで試すかというところで悩んだが、勘で２桁（1~99）にしたところ WA。何も考えずに３桁（1~999）にしたら AC した。計算量的には全然 OK なので問題なさそう（？？？）。
-
解答
Submission #2743100 - AtCoder Regular Contest 099
