トップ > AtCoder > ABC242D - ABC Transform

ABC242D - ABC Transform

AtCoder AtCoder-Beginner Contest 再帰 Python c++

【関連】
C - Large RPS Tournament

考え方

倍々に増えていく．逆に，再帰をすれば半分になっていく．$k \leq 10^{18} = 1000^{6} \sim 2^{60}$だから，60回再起すれば
  1. $S^{(t)}[0]$に行き着く（$S^{(t)}[0]$は$t$が増えるごとに$A\to B\to C$を繰り返すので求められる）か，
  2. 途中で$t=0$となる（これ以上遡れないが，$S^{(0)}[k]$は既知なので求められる）．


Editorial - AtCoder Beginner Contest 242を図示すると以下のようになる．

ABC242D


回答例 (Python)

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

def f(t, k):
  if t == 0:
    return ord(S[k]) - ord('A')
  if k == 0:
    return (ord(S[k]) - ord('A') + t) % 3
  if k % 2:
    return (f(t - 1, k // 2) + 2) % 3
  else:
    return (f(t - 1, k // 2) + 1) % 3

for _ in range(Q):
  t, k = map(int, input().split())
  print('ABC'[f(t, k - 1)])

回答例 (C++)

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

string S;

int f(ll t, ll k) {
  if (t == 0) {return S.at(k) - 'A';}
  if (k == 0) {return (S.at(k) - 'A' + t) % 3;}
  if (k % 2) {
    return (f(t - 1, k / 2) + 2) % 3;
  } else {
    return (f(t - 1, k / 2) + 1) % 3;
  }
}  

int main() {
  cin >> S;
  int Q; cin >> Q;
  string ABC = "ABC";
  
  while (Q > 0) {
    ll t, k; cin >> t >> k;
    cout << ABC.at(f(t, k - 1)) << endl;
    Q--;
  }
  return 0;
}

参考