Codeforces 5C: Longest Regular Bracket Sequence

Problem - C - Codeforces

Difficulty: 1900

問題概要

開きカッコと閉じカッコの２種類からなる文字列Sが与えられる．この文字列の部分文字列で，"対応が取れている"ものの中で最も長いものの文字列長と，その数を答えよ．

ただし，"対応が取れている"文字列とは，どの地点まででも閉じカッコの数が開きカッコの数より大きくならず，2種類の文字列の数が同じものである．

解法

DP的なイメージで解く．

まず，どのような部分文字列をとっても，ある閉じカッコに対応する開きカッコは不変であることがわかる． ある閉じカッコ(S[i])に対して，dおよびcを次のように定める．

d[i] := 対応する開きカッコの場所(存在しないなら-1)

c[i] := 閉じカッコS[i]で終わるような"対応が取れている"文字列のうち，最も長いものの始点

dはスタックを使えば容易にわかる．c[i]はd[i]であるか，それより左の可能性がある． 具体的には，c[d[i]-1]である．

後は文字列を前から順に見ていき，dおよびcを更新していけば良い．答えはcを見ることで得られる．

int d[1123456] = {};
int c[1123456] = {};

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int len = S.length();

    REP(i,1123456) c[i] = -1;

    stack<int> st;
    REP(i,len){
        if(S[i] == '('){
            st.push(i);
        }else{
            if(st.empty()){
                d[i] = -1;
            }else{
                int x = st.top();
                st.pop();
                d[i] = x;
                c[i] = d[i];
                if(c[x-1] != -1){
                    c[i] = min(c[x-1],d[i]);
                }
            }
        }
    }

    map<int,int> mp;
    int ans = -INF;

    REP(i,len){
        if(S[i] == '(') continue;

        if(c[i] == -1) continue;

        if(ans < i-c[i]+1){
            ans = i - c[i] + 1;
            mp[ans]++;
        }else if(ans == i -c[i]+1){
            mp[ans]++;
        }

    }
    if(ans == -INF){
        cout << "0 1" << endl;
        return 0;
    }

    cout << ans << " " << mp[ans] << endl;
}