Codeforces #350 Div2. E. Correct Bracket Sequence Editor

無駄に実装頑張ったけど不要だった。
http://codeforces.com/contest/670/problem/E

問題

括弧の整合性が取れた文字列Sが与えられる。
この文字列を編集したい。
初期状態でP番目の文字にカーソルが当たっている。

以下の各コマンドを処理し、最終的な文字列を出力せよ。

• カーソルを1字右に動かす。
• カーソルを1字左に動かす。
• カーソルの位置と、括弧の対応が対になる文字の間の部分文字列を削除する。カーソルは消した文字列群の右に移動する(右端を消した場合は左に移動)

解法

括弧の対応を取った後は愚直にシミュレートするだけ。
自分は双方向リストでやったが、setで未削除文字のindexを管理しても間に合うようだ。
削除する文字は高々O(|S|)個だしね。

int N,M,P;
string S;
string Q;

int le[505050],ri[505050];
int p[505050];
int is[505050];

void del(int cur) {
	is[cur]=0;
	if(P==cur) P=(ri[P]!=N+1)?ri[P]:le[P];
	ri[le[cur]] = ri[cur];
	le[ri[cur]] = le[cur];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>P;
	cin>>S>>Q;
	vector<int> st;
	FOR(i,N) {
		le[i+1]=i;
		ri[i+1]=i+2;
		is[i+1]=1;
		if(S[i]=='(') st.push_back(i+1);
		else p[i+1]=st.back(),p[st.back()]=i+1,st.pop_back();
	}
	FORR(r,Q) {
		if(r=='R') P=ri[P];
		if(r=='L') P=le[P];
		if(r=='D') {
			x=P;
			y=p[P];
			for(i=min(x,y);i<=max(x,y);) j=ri[i], del(i), i=j;
		}
	}
	FOR(i,N) if(is[i+1]) _P("%c",S[i]);
	_P("\n");
	
}

まとめ

set解法に無駄にHack仕掛けなくてよかった。TLEしないのね。