AtCoder Beginner Contest 350, F : Transpose

問題文

　https://atcoder.jp/contests/abc350/tasks/abc350_f

問題概要

　英大文字・英小文字・括弧 ((, )) からなる文字列 $S$ が与えられる．括弧の対応は正しくとれている．
　$S$ に対し，次の操作を可能な限り行う．

1. 内側に括弧を含まない（この順で出現する）(, ) を選ぶ．
2. その括弧内側の各文字（必ず英文字である）の大文字・小文字を相互に変換する．
3. その括弧の内側の文字列を反転する．
4. その括弧を削除する．

　操作完了後の文字列は一意に定まるので，それを求めよ．

制約

• $1 \leq |S| \leq 5 \times 10^5$

解法

　毎回の反転操作を実際に行ってしまうと最悪ケースで $\Theta( |S|^2 )$ 時間かかる入力を作れてしまうのでそれはまずくて，問題文で言われた通りの手順ではない方法で結果を得る必要があります．
　まず英文字に関する操作に着目します．大文字・小文字の反転の方は分かりやすくて，反転の回数は「その文字がある位置の括弧の深さ」と等しくなります．よって，深さが偶数の位置にある文字は元の文字と同じまま残り，奇数の位置では大文字・小文字変換された文字になります．
　反転については，「括弧の中身を反転する」代わりに「括弧の中身を逆順に読む」とすれば，実際の反転を行わずに反転後の文字列を構成できます．具体的にどう実現するかですが，「（現在の向きを基準に）開き括弧を見つけたら，対応する閉じ括弧の位置に飛び，向きを反転する」という操作を組み込んで舐めればよいです．そのためには括弧の対応を事前に計算しておく必要がありますが，これは，括弧列を扱うときの定石である^[要出典]ところの，スタックを使うことで実現できます．具体的には，開き括弧を見つけたらその添字（位置）をスタックに積み，閉じ括弧を見つけたらスタックトップの位置と対応していることが分かる（その後，スタックから pop する）というものです．この情報を使って，現在位置・向き・括弧の深さを引数にもつ再帰関数を実装することで，上記のような「括弧を見つけたら飛ぶ走査」を実装できます．この走査の途中で英文字を見つけるたびにその位置と括弧の深さを書き下せば，（問題文で言うところの）操作完了後の文字列での出現順序とその大文字 or 小文字が分かります．
　計算量についてですが，前計算のスタックを用いた括弧の対応の解析は文字列を先頭から末尾まで舐め，各位置で $O( 1 )$ 時間のスタック操作を定数回行うので，$\Theta( |S| )$ 時間です．再帰関数で文字列を走査するところも，各文字を高々一度ずつしか見ないので $\Theta( |S| )$ 時間となり，従って全体でも $\Theta( |S| )$ 時間です．

コード

　以下の実装では，「英文字の ASCII コードの $6$ ビット目をビット反転すると大文字・小文字が入れ替わる」というのを使っています．

int matches[ 1 << 19 ], oe[ 1 << 19 ];
VI order;

void solve( const string &S, const int i = 0, const int dir = 1, const int depth = 0 )
{
	if ( i == SZ( S ) )
	{
		return;
	}

	oe[i] = depth % 2;

	if ( ( dir == 1 && S[i] == '(' ) || ( dir == -1 && S[i] == ')' ) )
	{
		solve( S, matches[i] - dir, dir * -1, depth + 1 );
		solve( S, matches[i] + dir, dir, depth );
		return;
	}
	if ( ( dir == 1 && S[i] == ')' ) || ( dir == -1 && S[i] == '(' ) )
	{
		return;
	}

	order.PB( i );
	solve( S, i + dir, dir, depth );
	
	return;
}

int main()
{
	IN( string, S );

	stack< int > stk;
	REP( i, SZ( S ) )
	{
		const char c = S[i];

		if ( c == '(' )
		{
			stk.push( i );
		}
		else if ( c == ')' )
		{
			const int j = stk.top();
			stk.pop();

			matches[i] = j;
			matches[j] = i;
		}
	}

	solve( S );

	string res;
	FOR( i, order )
	{
		res += S[i] ^ ( oe[i] ? 1 << 5 : 0 );
	}
	cout << res << endl;

	return 0;
}