☆(途中)数学的考察(ARC099D - Snuke Numbers)

問題

D - Snuke Numbers

この回は確か参加したけどこれが解けなくて、まあギリギリ冷えなかった回。完全に忘れたので一から解いて行く。
これも含めてなのですが、最近のコンテストで冷えがちなのは500点（DかE）が数学的な問題で、数学的センスが壊滅的だからだという感じがします。まあAtCoderの問題は400点以下では全く数学的考察をしないことがほとんどなので、競技プログラミングで数学センスを使うのに慣れていないだけかもしれないという希望にかけて精進していきたいと思います。

すぐ分かること

f(n)=n/S(n)とする

の一の位以外が同じ時、。よってsnuke数となりうるのは一桁の数を除いては一の位が9の数字だけなので、以下ではそのような数字のみ考える。（なお一の位が9の全てのnより大きな数字に付いて式が成り立っていれば、とうぜん一の位を変えた全ての数字についても式が成り立つので）

の一の位が9で十の位のみ違う時、。
なぜならとすると、

よっての時、この式はだからです。
ここまでは誰でもわかります。

正しい解法

下の解法を考えた後にeditorialを見たら全く違うやり方で解いていました。
nがsnuke数の時、次のsnuke数はnのd(d=1,2,.....<=15)桁めを変更して0~d桁目を9にした数のうちどれかということを証明できます。よって15回以内f(m)を計算すれば次のsnuke数がわかる。

確かに、私が考えた解放の途中で出てきたように。S(n)が同じ時nが小さいほどいいのだから、必然的に?999とかになるのは
う〜ん、最初に一の位を示した感じでもっと粘り強くやってればすぐ思いついたのかな。数学力が足りないのかもしれない

考えた解法

もしかしたらTLEするかも
ここで、すでにsnuke数だとわかっている最大の数字n（最初は9）について、それ以降のsnuke数は全てそのsnuke数よりf(n)が大きいです。次のsnuke数は、それ以降のsnuke数のうちで最もf(n)が小さいものです。
ここで、それぞれのS(m)の値について、n以上のmのうち最もf(m)が小さい値を求めることができます。S(m)が同じ値ならmが小さいほどf(m)も小さいです。そのため、それぞれのS(m)について最もmが小さい値を求めてf(m)を計算し、一番f(m)が小さいもののうち最も小さいmを次のsnuke数に選びます。さらに、今準備されているmが選ばれた次のnより小さいS(m)についてだけ更新し…とします。
一回の更新はた　ぶ　ん　定数、K回数の計算量でできます（ループKは出力に必要なのでTLEではないでしょう。）

心配になるのは、10^15以上のmのf(m)について考えていないので、このf(m)よりf(n)が大きいためにsnuke数になれないものがあるのではないかということですが、K番目のsnuke数が10^15以下という条件からこの可能性は否定されます、any of your output<=f(snuke_K)<=f(any number > 10^15)だからです。

S(m)がわかっている時、Nより大きいmのうち最も小さいもの(ただし一の位は9)を調べるのとかちょっとめんどくさい気がするしう〜ん

コード

解法さえわかってしまうと普通に実装できるのでしません、忘れた頃にまたします。考察力をつけたい