TopCoder SRM 688 Div1 Medium ParenthesesDiv1Medium、Div2 Hard ParenthesesDiv2Hard

うーん、本番はあと一歩だった。
https://community.topcoder.com/stat?c=problem_statement&pm=14230
https://community.topcoder.com/stat?c=problem_statement&pm=14228

問題

括弧で構成された文字列Sと、文字列のindexの対(L[i],R[i])からなるクエリ群が与えられる。
各クエリに対し、部分文字列S[L[i]...R[i]]がいずれも括弧の対応が取れた文字列となるよう、Sの内容を変更したい。

条件を満たすよう、S内の２か所の文字をswapする場合、最小何回のswapで全クエリを満たすことができるか。
Div2は文字列長・クエリ数が少ないうえ、クエリ同士の範囲が交差しない。

解法

２つのクエリ(L[i],R[i]),(L[j],R[j])が共に部分的に共通部分を持っていると面倒なので、これをバラすことを考えよう。
例えばL[i]＜L[j]＜R[i]＜R[j]であることを考える。
この時、S[L[j]...R[i]]の範囲では開き括弧と閉じ括弧の対応が取れていないと、どちらかのクエリでは条件を満たせない。
よってこの２つのクエリは共通部分を持たない(L[i],L[j]-1),(L[j],R[i]),(R[i]+1,R[j])の３つに分解できる。
片方のクエリに別のクエリが完全に含まれるケースは気にしなくてよい。

このように分解し、部分的に範囲が交差することの無いようにしよう。
その後、Sに対し処理を行う。
クエリの区間の短い順に、以下をそれぞれ数えよう。

• 開き括弧を閉じ括弧にしなければいけない数
• 閉じ括弧を開き括弧にしなければいけない数

片方のクエリが別のクエリを含む場合、区間の小さい方のクエリに含まれる部分文字列は、区間の大きい方のクエリの処理ではいじってはいけない点に注意。

各クエリに対し上記数をそれぞれ足し、その和を取ろう。
前者が後者より多い場合、文字列中のクエリ対象外の文字に閉じ括弧が余っているならば、そこから閉じ括弧を持ってくるようにしよう。逆も同様。
そのようにして両者の数を揃えたらそれが解。

class ParenthesesDiv1Medium {
	public:
	pair<int,int> dodo(string& S,int L,int R) {
		int H[2020]={};
		int i;
		string T;
		for(i=L;i<=R;i++) if(S[i]!='*') T+=S[i],S[i]='*';
		FOR(i,T.size()) H[i+1]=H[i]+((T[i]=='(')?1:-1);
		int up=0,down=0,cur=0;
		FOR(i,T.size()) {
			if(T[i]==')') {
				if(cur==0) up++,cur++;
				else cur--;
			}
			else {
				if(cur+1>T.size()-i-1) down++,cur--;
				else cur++;
			}
		}
		return {up,down};
	}
	
	int minSwaps(string s, vector <int> L, vector <int> R) {
		vector<int> RR[2020];
		vector<pair<int,int>> req;
		int I[2020] = {};
		int Q=L.size();
		int N=s.size();
		int i,j,x;
		
		FOR(i,N) RR[i].clear();
		FOR(i,Q) RR[L[i]].push_back(R[i]);
		FOR(i,N) if(RR[i].size()) {
			sort(RR[i].begin(),RR[i].end());
			RR[i].erase(unique(RR[i].begin(),RR[i].end()),RR[i].end());
			
			for(j=1;j<RR[i].size();j++) RR[RR[i][j-1]+1].push_back(RR[i][j]);
			RR[i].resize(1);
			x=RR[i][0];
			for(j=N-1;j>i;j--) if(RR[j].size() && RR[j].back()>=RR[i][0]) x=min(x,j-1);
			if(x<RR[i][0]) {
				RR[x+1].push_back(RR[i][0]);
				RR[i][0]=x;
			}
			req.push_back({RR[i][0]-i,i});
			for(j=i;j<=RR[i][0];j++) I[j]=1;
		}
		
		int fu=0,fd=0;
		FOR(i,N) if(I[i]==0) ((s[i]=='(')?fu:fd)+=1;
		
		int up=0,down=0;
		sort(req.begin(),req.end());
		FORR(e,req) {
			if((e.first % 2) == 0) return -1;
			x = e.second;
			auto ret=dodo(s,x,RR[x][0]);
			up+=ret.first;
			down+=ret.second;
		}
		
		if(up>=down) return (fu>=up-down) ? up : -1;
		else return (fd>=down-up) ? down : -1;
	}
}

まとめ

本番交差するケースは考慮できたが、片方に片方が含まれるケースを読み切れなかった。