AtCoder Beginner Contest 242 D問題 ABC Transform

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

${\tt A}, {\tt B}, {\tt C}$ からなる文字列 $S$ が与えられる. 文字列の列 $S^{(0)}, S^{(1)}, S^{(2)}, \dots$ を以下のようにして生成する.

$S^{(0)}:=S$
$S^{(t)}$ は $S^{(t-1)}$ の各文字において, ${\tt A}$ を ${\tt BC}$ に, ${\tt B}$ を ${\rm CA}$ に, ${\tt C}$ を ${\tt AB}$ に同時に置き換えてできる文字列.

次の $Q$ 個の問 $q=1,2, \dots, Q$ に答えよ.

$S^{(t_q)}$ の先頭から $k_q$ 文字目は何か?

制約

$S$ は ${\tt A}, {\tt B}, {\tt C}$ からなる文字列
$1 \leq S \leq 10^5$
$1 \leq Q \leq 10^5$
$0 \leq t_q \leq 10^{18}$
$1 \leq k_q \leq \min \left(10^{18}, \left|S^{(t_q)} \right| \right)$

解法

${\tt A}':={\tt B}, {\tt B}':={\tt C}, {\tt C}':={\tt A}$ と書くことにする. また, 文字列 $T$ と $1 \leq k \leq |T|$ に対して, $T[k]$ で $T$ の $k$ 文字目を表すとする.

まず, $S^{(0)}=S$ であるから, 当然 $S^{(0)}[k]=S[k]$ が成り立つ.

そして, $S^{(t)}$ が $S^{(t-1)}$ のどこから発生しているか? そして, ${\tt A} \to {\tt B} \to {\tt C} \to {\tt A} \to \dots$ という構造に気がつくと,

$S^{(t)}=\begin{cases} S^{(t-1)} \left[\dfrac{k+1}{2} \right] ' & (k: {\rm odd}) \\ S^{(t-1)} \left[\dfrac{k}{2} \right] '' & (k: {\rm even}) \\\end{cases}$

である.

また, 1文字目については上の漸化式から, $S^{(t)}[1]=S^{(0)}[1]^{\underbrace{'' \dots ''}_t}$ であることもわかる.

以上から,

$S^{(t)}[k]=\begin{cases} S[k] & (t=0) \\ S^{(0)}[1]^{\underbrace{'' \dots ''}_t} & (k=1) \\ S^{(t-1)} \left[\dfrac{k+1}{2} \right] ' & (t \gt 0, k \gt 1, k: {\rm odd}) \\ S^{(t-1)} \left[\dfrac{k}{2} \right] '' & (t \gt 0, k \gt 1, k: {\rm even}) \end{cases}$

となる.

これを計算すればよいのだが, $S^{(t_q)} [k_q]$ を求めようとすると, 最終的にはある整数 $j$ とある非負整数 $p$ を用いて, $S^{(t_q)} [k_q]=S[j]^{\underbrace{'' \dots ''}_p}$ となるとわかる. 結局はこの $j,p$ を求めればよく, これから答えるべき文字を求めることもできる.