I know the k-th integer (PKU 3725)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3725

問題

1〜nまでの数字を辞書順に並べた時、mがk番目の数値となるとする。k,mが与えられるので最小のnを求める問題。
1<=k,m<=10^9

解法

nを二部探索し、nを固定した場合にmが何番目にくるかを考える。
1〜nまでの数字を桁数で分解し[1,9],[10,99],...,[10^log(n),n]という風にする。
[10000,99999]等の数値を辞書順に並べた時にmより前に来る数値の個数はO(log(n))で求めることが出来る。([10^log(n),n]の部分も)
なので全体でO(log^3(n))で求めることが出来る。
しかしこれでは間に合わないので、[1,9],[1,99],[1,999],...の部分を前もって計算することによりO(log^2(n))に計算量を減らし時間内に計算を終わらせることができる。