裏紙

ほぼ競プロ、たまに日記

SRM 670 Div1 Easy - Bracket107

問題

TopCoder Statistics - Problem Statement

問題概要

() のみで構成された文字列sが与えられる。いま、"correct bracket sequences"なる文字列を定義する。文字列全体として(の数と)の数が一致し、すべてのprefixに対して(の数のほうが)の数よりも多くなっているものである。

sと同じ長さの文字列tを考える。tが"correct bracket sequences"であり、sには一致せず、Longest Common Subseqence(LCS)の長さが最大になるものは何通りあるか。

  •  4 \le |s| \le 50

イデア

まずsの長さをnとすると、stのLCSの長さとしてはあり得るものの最大値はn-1である。実はLCSの長さがn-1となるような条件を満たす文字列tが必ず存在する。

LCSがn-1となるような条件を満たす文字列tが存在すると仮定すると、stから1文字ずつ取り除く事によって全く同じ文字列を作り出すことが出来るということを意味している。つまり、sから1文字取り除いて、別の部分に1文字付け足す事によってtの候補を生成することが可能になるのである。

ただ、バランスを保つ必要があるので、この問題においてはsから(を取り除いた時には(を付け足してtを作る必要がある、逆も然り。移動によって生み出される文字列が全てsと異なる保証はないが、制約からしてこの取り除いて別の部分に付け足すという行為を全ての位置に対して試せば少なくとも1つは条件を満たしつつsとは異なる文字列を作ることが可能である。

つまり、このようにして作成された文字列のうちで、sと一致すること無く"correct bracket sequences"であるものの中で異なる種類の個数を求めれば良いことになる。そのようなものをsetを使ってもとめると分かりやすい。

実装

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

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

class Bracket107 {
    public:
    bool correct(string s){
      int op=0;
      bool v=true;
      for(int i=0; i<s.size(); ++i){
        if(s[i]=='(') ++op;
        else --op;

        if(op<0){
          v=false;
          break;
        }
      }

      if(op!=0) v=false;
      return v;
    }

    int yetanother(string s) {
      int i,j;

      int n=s.size();
      set<string> strs;
      rep(i,n){//sのi文字目を抜く
        string t=s.substr(0,i)+s.substr(i+1);
        rep(j,n-1){//j文字目の手前に挿入(最後尾への挿入はムダ)
          string cand=t.substr(0,j)+s.substr(i,1)+t.substr(j);
          if(cand!=s && correct(cand)){
            strs.insert(cand);
          }
        }
      }

      return strs.size();
    }
};