torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AtCoder Beginner Contest 380, D : Strange Mirroring

問題概要

 英小文字からなる文字列 $S$ が与えられる.$S$ に対し,以下の操作を十分大きい回数繰り返し適用する:

  1. $S$ の大文字・小文字を反転した文字列を $T$ とする.
  2. $S \leftarrow S + T$ とする.

 $q$ 個の整数 $K_1, K_2, \dots, K_q$ が与えられる.各 $K_i$ に対し,$S_k$ を求めよ.

制約

  • $|S| \leq 2 \times 10^5$
  • $1 \leq q \leq 2 \times 10^5$
  • $1 \leq K_i \leq 10^{ 18 }$

解法

 各 $K_i$ について独立に答えが定まるため,着目している $K_i$ を $k$ と書きます.
 入力で与えられた時点での $S$ の長さを $l$ とします.$k \leq l$ であれば,$S_k$ がそのまま答えとなります.そうでない場合,$k$ が初めて「確実に有効な $S$ の添字」となる反復が存在するはずです(具体的には $k \leq l2^x$ となる最小の $x$ について $x$ 回目の反復).そのときの $S, T$ を考えると,

  • $k \leq |S|$ のとき,$S_k$ が答え.
  • $|S| < k$ のとき,$S_{ k - |S| }$ を反転したものが答え.

として,反復操作を巻き戻せます.このとき,$k$ の上界と「その反復での $S, T$」の長さは半分になっていくので,$O( \log k )$ 回の巻き戻しでベースケースに辿り着きます.
 上記は基本的な演算のみで実装できるため,各 $K_i$ ついて適用することで $O( q \log \max K )$ 時間のアルゴリズムとなります.
 実装についての小話としては,ASCII コードにおける大文字・小文字の反転は,文字コードの $6$ ビット目を反転することで行えます.

コード

int main()
{
	IN( string, S );
	IN( int, Q );
	VLL K( Q );
	cin >> K;

	const int L = SZ( S );
	
	vector< char > res;
	FOR( k, K )
	{
		LL l = L;
		for ( ; l < k; l *= 2 );

		int flip = 0;
		while ( L < k )
		{
			if ( l / 2 < k )
			{
				k -= l / 2;
				flip ^= 1;
			}
			l /= 2;
		}

		res.PB( S[ k - 1 ] ^ ( flip << 5 ) );
	}

	cout << res << endl;

	return 0;
}