Codeforces #626 Div1 A. Unusual Competitions

変則的な時間なので不参加だけども。
https://codeforces.com/contest/1322/problem/A

問題

カッコ列が与えられる。
ある長さLの連続部分列を並べ替えるコストをLとする。
カッコ列が正しくなるように並べ替えを繰り返したとき、総コストの最小値を答えよ。

解法

開き括弧と閉じ括弧の数が等しくないならそもそも解なし。
それ以外は、前から見て行ってprefixにおいて閉じ括弧の方が多くなったら、括弧のバランスがとれるところまでを並べ替えるようにしよう。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	int A=0;
	FORR(c,S) {
		if(c=='(') A++;
		else A--;
	}
	if(A!=0) return _P("-1\n");
	
	int ret=0;
	FOR(i,N) {
		if(S[i]=='(') {
			A++;
		}
		else if(A>0) {
			A--;
		}
		else {
			for(j=i;j<N;j++) {
				if(S[j]=='(') A++;
				else A--;
				if(A==0) break;
			}
			ret+=j-i+1;
			i=j;
			
		}
	}
	cout<<ret<<endl;
}

まとめ

まぁA問題だしまだ簡単。