[Yukicoder] チャンパーノウン定数

チャンパーノウン定数自体は既出のネタ(例：Project Euler 40)なので、基本的には以下の方針で良い(CodeIQコード銀行「n番目の数字は？」(答案)のコメントより)。

1
2
3
4
5
6
7
8

例えば1から999までは以下の様な区間に分割できる。
1 + 0〜8
10 + 0〜89
100 + 0〜899
各区間に含まれる数字の個数は9、180、2700となる。
これを1*1*9、2*10*9、3*100*9と表現する(digits*expbase*9)。
入力値が入る区間が決まったら、それより下の和を入力値から引き(nとする)、
(digits)桁の数を並べた中のn桁目を求めれば良い。

これで、ビルトイン多倍長整数を使えば10**1000程度まではACできる。ただし、今回は入力が非常に大きいため、下位から順番に処理すると多倍長演算が容易にTLEを招いてしまう(解答例のif falseの一部)。 まず、この1*1*9 + 2*10*9 + 3*100*9 + ...を高速に求めることを考える。

1
2
3
4

Sn   = 1*1*9 2*10*9 3*100*9 4*1000*9
10Sn =       1*10*9 2*100*9 3*1000*9  4*10000*9
-9Sn = 1*1*9 1*10*9 1*100*9 1*1000*9 -4*10000*9
-9Sn = (10**4-1)                     -4*10000*9

といった変形により、Si = i*10**i - (10**i-1)/9と定式化できる。これを用いて、digitsを2分探索するか上位から探索するかする。これでTLEを回避できる。