問題

$10^{16}$ 個の問題が次のように ID が次のような順番で付されている.

では, ID に割り当てられている文字列 $S$ が与えられるので, $S$ が ID になっているのは何問目か?

$S$ の長さを $N$ とする. このとき, 長さが $N$ 未満の英大文字列の個数 $X$ は

$\displaystyle X=\sum_{i=1}^{N-1} 26^i$

である.

また, 長さが $N$ で辞書式で $S$ 未満の英大文字列の数は $S$ の各文字について, ${\tt A} \to 0, {\tt B} \to 1, \dots {\tt Z} \to 25$ と変換した整数列を $T=(T_1, \dots, T_N)$ としたとき,

$\displaystyle Y=\sum_{i=1}^N 26^{N-i} T_i$

である.

以上を用いて, 求めるべき解答は $(X+Y+1)$ となることがわかる.

計算量は $O(N)$ 時間である.

Kazun の競プロ記録