Bracket Sequence Deletion-Codeforces

問題リンク-Bracket Sequence Deletion

問題

(と)からなる$n$文字の文字列が与えられます。
以下の操作をできる限り繰り返します。

操作：与えられた文字列から条件を満たす最小の接頭辞を取り除く。

条件は以下の2つのうちどちらか1つを満たせば良いです。

• 接頭辞が通常の括弧列である
• 接頭辞が回文である

通常の括弧列であるとは、数学的に正しい表現であることをいう。()や(()(()))など。
回文であるとは、逆から読んでも同じであることをいう。)))や)(()など。

操作回数と残った文字列の数を出力する。

接頭辞：文字列の先頭から始まる部分文字列。

解法

接頭辞の1文字目で場合分けをします。

接頭辞の1文字目が(だった場合

次の文字が)となれば、()となり通常の括弧列という条件を満たします。また、(の場合でも((となり回文の条件を満たします。
したがって、この場合は次の文字が存在すれば、2文字取り除くことができます。

3文字以上取り除くことがない理由：問題文より最小の接頭辞とありこれ以上増やせないからです。

接頭辞の1文字目が)だった場合

この場合、括弧が閉じることはないので通常の括弧列になることはありません。したがって、回文の条件を満たす最小の範囲を見つけ取り除きます。
最小の範囲は次の)が見つかるまでです。次の)が現れるまでは(しか現れないので文字数などによらず回文が成立します。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;

    int p = 0;
    int ope = 0;
    while(p+1 < n){
        if(s[p] == '('){
            p += 2;
        }else{
            int r = p+1;
            while(r < n && s[r] != ')'){
                r++;
            }
            if(r == n)break;
            p = r+1;
        }
        ope++;
    }
    printf("%d %d\n", ope, n-p);
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}