公式

D - ABC Transform 解説 by en_translator


Preface

In this editorial, we use \(0\)-based index, instead of \(1\)-based index, for \(S\). In other words, when the length of \(N\) is \(S\), \(S = S_1 S_2 \ldots S_N\), not \(S = S_0 S_1 \ldots S_{N-1}\).

Body

Let \(f(t,k)\) be “the function that returns the \(k\)-th character of \(S^{(t)}\).”

First, for \(t = 0\), \(f(t,k)\) is the \(k\)-th character of \(S\).

Next, we consider the case where \(k = 0\). Taking a closer look, we can see that the \(0\)-th characters of \(S^{(0)}, S^{(1)}, S^{(2)}, S^{(3)}, S^{(4)} \ldots\) are either

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

which are periodic.

If the successor of A is defined to be B, B is C, and C is A, then the \(0\)-th character of \(S^{(t)}\) is the \(t\)-th successor of the first character of \(S^{(0)}\).

Therefore, when \(k = 0\), \(f(t,k)\) is the \(k\)-th successor of \(S_0\).

Finally, let’s consider what \(f(t,k)\) returns when \(0 \lt t,k\).

Taking a closer look again, we can see that

  • when \(k\) is even, \(f(t,k)\) is the first successor of \(f(t-1,\frac{k}{2})\);
  • when \(k\) is odd, \(f(t,k)\) is the second successor of \(f(t-1,\frac{k}{2})\).

Thus, for \(0 \lt t,k\), we can recursively obtain \(f(t,k)\) based on the value of \(f(t-1,\lfloor \frac{k}{2} \rfloor)\). Here, \(\lfloor \frac{k}{2} \rfloor\) is \(\frac{k}{2}\) rounded down.

Therefore, \(f(t, k)\) is

  • the \(k\)-th character of \(S\) if \(t=0\);
  • the \(k\)-th successor of \(S_0\) if \(k=0\);
  • the (remainder of \(k\) by \(2\), plus \(1\))-th successor of \(f(t-1,\lfloor \frac{k}{2} \rfloor)\) if \(t=0\).

We can code the procedure as follows.

Sample code (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;
	}

}

The time complexity is \(O(N + Q \log (\max(k)))\), because for each query the function \(f\) is called at most \(O(\log k)\) times.

This is very fast, even in PyPy3 where recursive function is generally said to be slow:

Sample code (PyPy3)

投稿日時:
最終更新: