こう考えた
まず最初にこの問題のA,B,Cをそれぞれ0,1,2と呼ぶことにします。一般性を失いません。
また、次の節で述べる通り、$t=0,1,2,3...$のことを上から積み重ねた"段"と呼ぶことにします。
k文字目の段を降りたときの周期性
最初にシミュレーションしてみます。
s = "A"
s = s.replace("A", "0").replace("B", "1").replace("C", "2")
for i in range(6):
print(i, s)
s = s.replace("0", "x").replace("1", "y").replace("2", "z")
s = s.replace("x", "12").replace("y", "20").replace("z", "01")
print(" ", s)
実行します。
0 0
1 12
2 2001
3 01121220
4 1220200120010112
5 20010112011212200112122012202001
01121220122020011220200120010112122....
この時、ぱっとみて気が付くのは、
- ある文字が決まると、段(t)を重ねるごとに
0->1->2と進む
この特性は後で利用します。
次に上記のforループの値を大きくすると、
- 段数を増やしていくと、
1文字 -> 2文字 -> 4文字 -> 8文字のように文字数が2の累乗で変化
つまり、$t$段目の文字数は$0$段目の文字数を$n$とすると、$n \times 2^t $文字であることが分かります。
今回の問題では、$k \leq 10^{18}$なので、高々60段目でk文字目は必ず存在します。($2^{60}$は大体$1.1 \times 10^{18}$です)
60段目までにおけるk文字目を求める
さて、上の実行例は左寄せでprintしましたが、これを木のように書いてみることにしましょう。つまり、以下のようにします。そして、じっと睨みます。
指摘いただきましたが最後の段のind3 は2です。直しますが、今元画像がないので取り急ぎ文章にて。
すると、以下のことが分かります。
- あるノードはその親のノードの値に対して、自分が左なら+1, 右なら+2して$mod3$したもの
- 少しにらむと、ノード番号$i$が偶数なら親から見て左のノード、奇数なら右のノードであることが分かります
- この木のノードは(葉を除き)ちょうど2つのノードを持つ。(つまりセグメントツリーのように)上の段の親のノード番号はそのノード番号を$i$としたとき、$i//2$(切り捨て)となる。
つまり、ある$0 < t$段目のノードind=$i$の値を$f(t, i)$とすると、
- iが偶数の時: $f(t-1, i//2) + 1$の$mod3$
- iが奇数の時: $f(t-1, i//2) + 2$の$mod3$
- $t=0$というのは与えられた入力(を0,1,2にしたもの)そのもの
60段目よりも先を求める
この式を求めることで解けました...と言いたいですが、今回は$t \leq 10^{18}$と大きいので再帰すると非常に大きな回数のループを回すため計算が間に合いません。そこで最初に気が付いた、ある$k$文字目をそのまま1段下がると+1してmod3した値になる。という気付きを使います。つまり、$t$段$k$文字目の数が$val$とわかっているなら、$t+a$段目の$k$文字目は$val + a$のmod3であることが分かります。
次のようにします。
- $t \leq 60$ならシミュレーションします
- $t > 60$のとき、$t=60$での$k$文字目を調べた後、ほしい文字は$t-60$段下にあるのですから、
+(t-60)して、mod3します。
これで、$t$が非常に大きい時にも、60回程度のループで答えを求めることができました。
実装
s = input() # ABCを
s = s.replace("A", "0").replace("B", "1").replace("C", "2") # 012にして
s = list(s) # ["0", "1", "2"]にしてから
s = list(map(int, s)) # [0, 1, 2]にする
def f(t, i):
if t == 0: return s[i]
if t<=60:
if i % 2 == 0: return (f(t-1, i//2) + 1) % 3
else: return (f(t-1, i//2) + 2) % 3
else:
return (f(60, i) + (t-60)) % 3
q = int(input())
ansdict = {0:"A", 1:"B", 2:"C"} # 0,1,2をA,B,Cに戻す
for _ in range(q):
t, k = map(int, input().split())
k -= 1 # 1-indexed -> 0-indexed
print(ansdict[f(t, k)])