Codeforces Round #587 (Div. 3) E2. Numerical Sequence (hard version)

問題概要

正整数 $x$ に対して、 $1, 2, .., x$ を十進表記で書いたものをこの順に連結した文字列を $s(x)$ とする。例えば $s(11) =$ "1234567891011" である。

そして、 $s(1), s(2), ...$ をこの順に連結した無限の長さの文字列を考える。与えられる $q$ 個の整数 $k_{i}$ に対して、この文字列の $k_{i}$ 番目の文字を答えよ。

制約

$1 \le q \le 500$
$1 \le k_{i} \le 10^{18}$

解法

各クエリに対する $k_{i}$ を単に $k$ と記します。また、問題概要に記したように文字列 $s(x)$ を定めます。

まず、 $k$ 番目の文字がどの $s(x)$ に属するか調べる必要があります。これは $s(1), s(2), ..., s(x)$ の長さの合計を $S(x)$ とすると、 $S(x) \ge k$ を満たす最小の $x$ として求められるので二分探索できます。判定問題を解くために、ある固定した値 $x$ に対する $S(x)$ の効率的な求め方を考えましょう。

$x$ の桁数を $D$ として、 $1 \le d \le D$ なる桁数 $d$ を考えます。整数 $1, ..., x$ に含まれる $d$ 桁の値を抜き出します。この最小値、最大値、値の個数をそれぞれ $m_{d}, M_{d}, n_{d}$ と書くことにすると、これらは以下のように計算できます。

$m_{d} = 10^{d-1}$
$M_{d} = \min(10^{d}-1, x)$
$n_{d} = M_{d} - m_{d} + 1$

やりたいことは文字列 $s(m_{d}), ..., s(M_{d})$ の長さ合計を求めることです。これを $1 \le d \le D$ について合計したものが $S(x)$ になります。

ある $d$ についての計算を、さらに分けて考えます。 $1 \le e \le d$ なる桁数 $e$ について、文字列 $s(m_{d}), ..., s(M_{d})$ の中に $e$ 桁の整数が合計でいくつ入っているかを求めます。

$e \lt d$ のとき、 $s(m_{d}), ..., s(M_{d})$ それぞれに $e$ 桁の整数全てが1つずつ含まれています。 $e$ 桁の整数は全部で $9\times 10^{e-1}$ 種類あるので、合計で $9\times 10^{e-1} \times n_{d}$ 個の整数があります。
$e = d$ のとき、 $e$ 桁の整数は $s(m_{d})$ に1個、 $s(m_{d}+1)$ に2個、...、 $s(M_{d})$ に $n_{d}$ 個含まれています。つまり等差数列の公式から、合計で $\frac{1}{2}n_{d}(n_{d}+1)$ 個の整数があります。

これに $e$ を掛けたものを全ての $1 \le e \le d$ について合計すると $s(m_{d}), ..., s(M_{d})$ の長さ合計が求められます。それをさらに $1 \le d \le D$ について合計したものが $S(x)$ になります。

これを用いて二分探索することで、 $k$ 番目の文字がどの $s(x)$ に属するか求められました。ここで求められた値を引き続き $x$ と記します。ここで $k^{\prime} = k - S(x-1)$ とすると、求めたいのは $s(x)$ の $k^{\prime}$ 番目の文字です。

ここで知りたいのは $s(x)$ として並べられた整数 $1, 2, ..., x$ のうちどれに $k^{\prime}$ 番目の文字が含まれているかで、これはまたしても二分探索することで求められます。つまり $k^{\prime}$ 番目の文字を含むのは、 $|s(y)| \ge k^{\prime}$ を満たす最小の $y$ です。

$|s(y)|$ の計算方法は先ほどの $S(x)$ に比べると簡単で、 $1, ..., y$ の中に $d$ 桁の数がいくつ含まれるかを同じように計算し、それに $d$ を掛けたものを全て合計すれば良いです。

これで $y$ も特定できれば、その十進表記における $k^{\prime} - |s(y-1)|$ 番目の数字が求める文字です。

ACコード

Submission #61031718 - Codeforces

計算量ですが、 $q$ が小さいので10の冪乗などの前計算などをしておかなくても余裕があります。二分探索・桁数 $d, e$ の全探索・10の冪乗で $O(\log k)$ が4つくらい付いていると思います。

またオーバーフローに注意する必要があります。二分探索の初期値としてあまり大きな値を取りすぎると $S(x)$ の値がオーバーフローしますが、実際に計算すると $S(10^{9})$ がだいたい $4.39 \times 10^{18}$ になって $k$ の制約を超えるので、 $x$ の上側の初期値を $10^{9}$ としておくと良いでしょう。