はじめに

この解説において、\(S\) は 1-indexd ではなく 0-indexed であるとします。すなわち \(S\) の長さを \(N\) としたとき、\(S = S_1 S_2 \ldots S_N\) ではなく \(S = S_0 S_1 \ldots S_{N-1}\) となります。

本題

\(f(t,k)\) を、「\(S^{(t)}\) の \(k\) 文字目を返す関数」と定義しましょう。

まず、\(t = 0\) のとき、\(f(t,k)\) は \(S\) の \(k\) 文字目となります。

次に \(k = 0\) の場合について考えます。\(S^{(0)}, S^{(1)}, S^{(2)}, S^{(3)}, S^{(4)} \ldots\) の \(0\) 文字目は、じっくりと観察をすると

• A, B, C, A, B, \(\ldots\)
• B, C, A, B, C, \(\ldots\)
• C, A, B, C, A, \(\ldots\)

のいずれかになることが分かり、そしてその並びは周期的です。

A から \(1\) 進んだ文字が B、B から \(1\) 進んだ文字が C、C から \(1\) 進んだ文字が A であるとすると、\(S^{(t)}\) の \(0\) 文字目は \(S^{(0)}\) の \(0\) 文字目から \(t\) 進んだ文字に等しくなるとも言うことができます。

そのため \(k = 0\) のとき、\(f(t,k)\) は \(S_0\) から \(t\) 進んだ文字となります。

それでは最後に、\(0 \lt t,k\) のとき、\(f(t,k)\) が何を返すかを考えましょう。

こちらもじっくりと観察をすると、

• \(k\) が偶数のとき、\(f(t,k)\) は \(f(t-1,\frac{k}{2})\) から \(1\) 進んだ文字
• \(k\) が奇数のとき、\(f(t,k)\) は \(f(t-1,\frac{k-1}{2})\) から \(2\) 進んだ文字

になることが分かります。よって、\(0 \lt t,k\) のとき \(f(t,k)\) は \(f(t-1,\lfloor \frac{k}{2} \rfloor)\) の値を用いて再帰的に求めることが可能です。ここで、\(\lfloor \frac{k}{2} \rfloor\) は \(\frac{k}{2}\) の小数点以下を切り捨てた値です。

よってまとめると、

• \(t = 0\) のとき \(f(t,k)\) は \(S\) の \(k\) 文字目
• \(k = 0\) のとき \(f(t,k)\) は \(S_0\) から \(t\) 進んだ文字
• \(0 \lt t,k\) のとき \(f(t,k)\) は \(f(t-1,\lfloor \frac{k}{2} \rfloor)\) から \(k\) を \(2\) で割ったあまり \(+\ 1\) だけ進んだ文字

となります。

これをコードに起こすと以下のようになります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

int main(){
	
	string S; cin >> S;
	int Q; cin >> Q;

	auto g = [&](char s, ll add){
		return char('A'+(s-'A'+add)%3);
	};

	std::function<char(ll,ll)> f = [&](ll t, ll k){
		if(t == 0) return S[k];
		if(k == 0) return g(S[0],t);
		return g(f(t-1,k/2),k%2+1);
	};

	while(Q--){
		ll t,k; cin >> t >> k;
		cout << f(t,k-1) << endl;
	}

}

計算量は、一つのクエリあたり関数 \(f\) が高々 \(O(\log k)\) 回しか呼び出さいことを考えると、\(O(N + Q \log (\max(k)))\) となります。

これは非常に高速であり、一般に再帰関数が遅いとされる PyPy3 においても高速に動作します：

実装例 (PyPy3)