SRM 670 Div1 Easy - Bracket107
問題
TopCoder Statistics - Problem Statement
問題概要
(
と)
のみで構成された文字列が与えられる。いま、"correct bracket sequences"なる文字列を定義する。文字列全体として(
の数と)
の数が一致し、すべてのprefixに対して(
の数のほうが)
の数よりも多くなっているものである。
と同じ長さの文字列を考える。が"correct bracket sequences"であり、には一致せず、Longest Common Subseqence(LCS)の長さが最大になるものは何通りあるか。
アイデア
まずの長さをとすると、とのLCSの長さとしてはあり得るものの最大値はである。実はLCSの長さがとなるような条件を満たす文字列が必ず存在する。
LCSがとなるような条件を満たす文字列が存在すると仮定すると、とから1文字ずつ取り除く事によって全く同じ文字列を作り出すことが出来るということを意味している。つまり、から1文字取り除いて、別の部分に1文字付け足す事によっての候補を生成することが可能になるのである。
ただ、バランスを保つ必要があるので、この問題においてはから(
を取り除いた時には(
を付け足してを作る必要がある、逆も然り。移動によって生み出される文字列が全てと異なる保証はないが、制約からしてこの取り除いて別の部分に付け足すという行為を全ての位置に対して試せば少なくとも1つは条件を満たしつつとは異なる文字列を作ることが可能である。
つまり、このようにして作成された文字列のうちで、と一致すること無く"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(); } };