考察(ABC064D - Insertion)

atcoder.jp

え〜、なんかすぐ出来た。

括弧列であることと、(の個数と) の個数が同じで、さらに前から部分列を取得したときその部分列において( の個数が )の個数以上であることは同値である。
また、追加する個数が同じとき、(は先頭、)は末尾に持ってきても()の組が出来なくなることはない。よって(は先頭、)は末尾に追加していく。
よって解法としては、文字の間（先頭、末尾含む）を一つ一つ探索する。その間より左の)の数が(より多いと、正しい括弧列が作れないので、その文(を先頭に追加。これを繰り返して最後に(の方が)より多くなってしまったら、その分)を末尾に追加すればいい。

計算量は

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long

int main(void){
    int N,s[105];
    char S[105];
    int r[105];//0~N-1の文字の左までの右にある文字カウント　'('-'')''
    int l[105];//0~N-1のもじの右までの左にある文字カウント
    scanf("%d",&N);
    scanf("%s",S);
    int t1=0,t2=0;
    rep(i,N){
        if(S[i]=='(')s[i]=1;
        if(S[i]==')')s[i]=-1;
        if(i==0)l[i]=s[i];
        else l[i]=s[i]+l[i-1];
    }
    rep(i,N){
        if(i==0)r[N-1-i]=s[N-1-i];
        else r[N-1-i]=s[N-1-i]+r[N-i];
    }
    
    rep(i,N+1){
        if(i==0){
            if(r[0]<0)t1=-r[0];
            if(l[N-1]+t1>0)t2=l[N-1]+t1;
        }else if(i==N){
            t2=l[i-1]+t1;
        }else{
            if(l[i-1]+t1<0){
                t1-=l[i-1]+t1;
            }
        }
    }
    rep(i,t1)printf("(");
    rep(i,N)printf("%c",S[i]);
    rep(i,t2)printf(")");
    printf("\n");
}