WARush

SRMの結果とか、解けた問題のコードを書いていきます

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();
    }
};