kmjp's blog

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

TopCoder SRM 670 Div1 Easy Bracket107

バグったコードが通ってしまって良順位。
http://community.topcoder.com/stat?c=problem_statement&pm=14059

問題

correct bracket sequenceを成している文字列Sが与えられる。
以下を満たすTは何通りあるか求めよ。

  • |S|==|T| だが S!=T
  • Tもcorrect bracket sequence
  • LCS(S,T)が、上記2条件を満たすTのうち最大

解法

LCS(S,T)=|S|-1となるTが常に生成できることを示す。

  • Tが"(())()"のように複数のcorrect bracket sequenceの連結を含む場合
    • 前半のcorrect bracket sequenceにある閉じ括弧を全体の末尾に持って行けば、元とは異なるcorrect bracket sequenceを生成できる。
  • Tが上記条件を満たさない場合は"(((())))"のようになっているので、末尾の閉じ括弧を適当な開き括弧の前に持って行って"((()()))"のようにすれば元とは異なるcorrect bracket sequenceを生成できる。

LCS(S,T)=|S|-1となるTが存在することが分かったので、Sから1文字総当たりで移動してLCS(S,T)=|S|-1となるTの候補を列挙する。
後はTの候補がcorrectか確認すればよい。
1文字動かした場合LCS(S,T)は|S|か|S|-1なのは明らかなので、S==Tの場合さえ除外すれば、実際にLCSを求める必要はない。

class Bracket107 {
	public:
	int yetanother(string s) {
		int L=s.size(),i,x,y;
		
		set<string> S;
		FOR(x,L) {
			string s1=s.substr(0,x)+s.substr(x+1);
			FOR(y,L) S.insert(s1.substr(0,y)+s[x]+s1.substr(y));
		}
		
		int ret=0;
		FORR(r,S) if(r!=s) {
			int ok=1;
			int cur=0;
			FORR(r2,r) {
				if(r2=='(') cur++;
				else cur--;
				if(cur<0) ok=0;
			}
			ret += ok;
		}
		return ret;
	}
}

まとめ

LCS求めるとO(|S|^4)、求めないとO(|S|^3)か。

S がもう少し大きいとチャレンジできたんだけどな。