ABC242D

ABC242D の解説

atcoder.jp

解答コード

https://atcoder.jp/contests/abc242/submissions/29888966

問題

文字列を規則的に変換し続ける問題です．
A -> BC
B -> CA
C -> AB

t 回変換したとのk文字目を出力します．

解説

t回目の変換をした後のk文字目が問われるので，
k文字目はt-1回の時点では何番目の文字だったのか？
t-2回目の時点では何番目だったのか?
t-3回目の時点では
（中略）
0回目の時点では何番目の文字だったのか？
を探します．

0回目の時点での文字が分かれば，
それをt回変換させることで，答えを導き出します．

概要図です．

ABC242D_overview

コードにします．

事前に変換操作に使用する辞書を定義します．

d = {'A': 'BC', 'B': 'CA', 'C': 'AB'}

このとき，変換は次のように行うことができます．

print(d['A'])
# BC

標準入力を読み取ります．

S = input()
Q = int(input())

Q回のクエリが与えられるので，forでQ回処理をします．
kを0-indexにするため，1だけ引きます．

for _ in range(Q):
    t, k = map(int, input().split())
    k -= 1

ここから，一旦議論箇所を絞るため，TLEになるコードを書きます．

for の中で，さらに以下のような処理を記述します．
t=tからt=0に向かって，何番目の文字を変換したのか辿ります．

    L = []  # indexを2で割った余りの数を記録しておく
    for i in range(t):
        L.append(k%2)  # 変換後は何文字目?
        k //= 2  # 変換前は何文字目?

t=0の時の文字の番号がわかるので，後はそれをt回変換することで，
処理をシミュレートできます．

    L = L[::-1]  # t=0の方から逆順で処理
    s = S[k]  # t=0のとき[k]文字目だった
    for l in L:  # t回変換する

        s = d[s][l]  # 変換した後の[l]文字目である
    print(s)

しかし，このままではTLEします．
なぜならt回の操作が非常に大きいからです．

この問題の変換操作は，1回の操作で文字列の長さが2倍になります．
つまり，t=0の時の1文字目はt=60回目で2^60 = 約10^18の長さになります．

よって，tが大きい時，t=0になるまでに，途中で[0]文字目になります．
その後は，先頭の文字しか追う必要しかありません．
先頭の文字だけ着目すると，
'A'を変換し続けると
'A' -> 'B' -> 'C' -> 'A' -> 'B' -> ...
と3回ごとにループすることから，愚直にシミュレートする必要がないことがわかります．

上記の内容を踏まえてコードにします．

事前に文字xを0, 1, 2回変換するとどうなるかを定義しておきます．

X = {
    'A': ['A', 'B', 'C'],
    'B': ['B', 'C', 'A'],
    'C': ['C', 'A', 'B']
    }

for 以下の内容は次のようになります．
0文字目になった段階で何番目の文字かを計算するプロセスを中断します．
ただし，中断した分の不足する変換回数分を算出します．
3回の変換で，もとの文字に戻るので，3で割ります．

for _ in range(Q):
    t, k = map(int, input().split())
    k -= 1
    L = []
    x = 0
    for i in range(t):
        L.append(k%2)
        k //= 2
        # 0文字目になれば，もうシミュレートする必要はない．
        if k == 0 and L[-1] == 0:
            # 残り何回変換するか．ただしMOD 3
            x = (t - i - 1)%3
            break
    L = L[::-1]
    # t=0の文字をx回(MOD 3)変換した文字
    s = X[S[k]][x]
    for l in L:
        s = d[s][l]
    print(s)

以上，ABC242Dの解法でした．

＜参考解説リンク＞