Codeforces #794 : Div1 C. Bring Balance

過去どこかで見ててもおかしくなさそうな問題。
https://codeforces.com/contest/1685/problem/C

問題

括弧列Sが与えられる。
このSは、開き括弧と閉じ括弧がN個ずつで構成されている。

Sの部分列を反転させる作業を行い、Sを正しい括弧列にしたい。
最小何回反転すればよいか。

解法

2手で必ず条件を満たせる。
開き括弧が先行する数が最多になるのがSのx文字のprefixである場合、先頭x文字と末尾(2N-x)文字それぞれを反転すると条件を満たす。
0手で満たすケースは自明なので、あとは1手で行けるか判定すればよい。

Sのprefixのうち、開き括弧が最も先行するprefixと、suffixのうち後ろから閉じ括弧が最も先行するsuffixを固定し、残りを反転させてチェックすればよい。

int T,N;
string S;
int A[202020];

int ok(string S2) {
	int cur=0;
	FORR(c,S2) {
		if(c=='(') cur++;
		else cur--;
		if(cur<0) return 0;
	}
	return cur==0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		int mi=0;
		FOR(i,2*N) {
			A[i+1]=A[i]+(S[i]=='('?1:-1);
			mi=min(mi,A[i+1]);
		}
		if(mi==0) {
			cout<<0<<endl;
			continue;
		}
		int L=0,R=2*N-1;
		FOR(i,2*N) {
			if(A[i]>=A[L]) L=i;
			if(A[i]<0) break;
		}
		for(i=2*N;i>=0;i--) {
			if(A[i]>=A[R]) R=i;
			if(A[i]<0) break;
		}
		string S2=S;
		reverse(S2.begin()+L,S2.begin()+R);
		if(ok(S2)) {
			cout<<1<<endl;
			cout<<(L+1)<<" "<<R<<endl;
			continue;
		}
		x=max_element(A,A+2*N+1)-A;
		cout<<2<<endl;
		cout<<1<<" "<<x<<endl;
		cout<<x+1<<" "<<(2*N)<<endl;
		
		
	}
}

まとめ

括弧列の問題、反転させたり開き括弧と閉じ括弧入れ替えたり色んなバリエーションありそう。