バグったコードが通ってしまって良順位。
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 | がもう少し大きいとチャレンジできたんだけどな。 |