SRM670 Div1 Easy "Bracket107"
解法
まず、文字列の長さをnとしたときに、LCSがn - 1なcorrect bracket sequenceは必ずある。
根拠は以下の通り
★任意の(を、それより前の位置にある)の前に持ってくることができる s=( ( ) ( ) ) ^ t=( ( ( ) ) ) ^ ★例外として((()))なやつは、任意の)を(の後に持ってくることができる s=( ( ( ) ) ) ^ t=( ) ( ( ) ) ^
よって、任意の文字1つを、任意の場所に移動させてLCSをn-1とした文字列を探索し、correct bracket sequenceであるものを数え上げればよい。
ソースコード
class Bracket107 { public: int yetanother(string s) { int n = s.size(); set<string> ansSet; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // i番目の文字をj番目に移動 string t = s; char c = t[i]; t.erase(i, 1); string cc(1, c); t.insert(j, cc); // 同じ文字列になってしまったら無視 if (s == t) continue; // correct bracket sequenceかな? int open = 0; for (int k = 0; k < n; k++) { if (t[k] == '(') { open++; } else { open--; } if (open < 0) break; } // correct bracket sequenceならばsetに追加 if (open == 0) ansSet.insert(t); } } return ansSet.size(); } };