kmjp's blog

競技プログラミング参加記です

TopCoder SRM 688 Div1 Easy ParenthesesDiv1Easy

この回はEasyもMediumも落としてグダグダ。
https://community.topcoder.com/stat?c=problem_statement&pm=14229

問題

括弧で構成された文字列が与えられる。
この文字列のうち連続した部分列に対して、順番を反転させたうえで閉じる開くを反転させるという処理を行える。

この処理を何度か繰り返して、文字列の括弧の対応が取れるようにしたい。
処理回数10回以内で条件を満たす処理手順を答えよ。

解法

元々開く・閉じるの対応がとれている部分文字列は、両方を含むような処理を行っても括弧の対応は変わらない。
そこで、まず初期状態で括弧の対応が取れているものは無視しよう。

すると、残りの文字列はprefixは閉じ括弧のみ、postfixは開き括弧のみとなる。
そこで、まず1回閉じ括弧群を反転させてすべて開き括弧とし、続いて開き括弧のうち後ろ半分を反転させればすべての括弧に対応がつく。
すなわち最大でも2回反転させれば十分である。

class ParenthesesDiv1Easy {
	public:
	
	vector <int> correct(string s) {
		int L=s.size();
		if(s.size()%2) return {-1};
		int i,j;
		
		vector<pair<char,int>> V;
		FOR(i,L) {
			if(V.size() && V.back().first=='(' && s[i]==')') V.pop_back();
			else V.push_back({s[i],i});
		}
		
		if(V.empty()) return {};
		vector<int> R;
		FOR(i,V.size()) if(V[i].first=='(') break;
		if(i!=0) {
			int x=V[0].second, y=V[i-1].second;
			R.push_back(V[0].second),R.push_back(V[i-1].second);
			FOR(j,i) V[j].second = y-(V[j].second-x);
			reverse(V.begin(),V.begin()+i);
		}
		R.push_back(V[V.size()/2].second);
		R.push_back(V[V.size()-1].second);
		
		return R;
	}
}

まとめ

そこまで難しい問題ではないのだけど、あっさりコーナーケースに引っかかってしまった。