ホームに戻る
括弧の問題
０、はじめに
括弧'('と')'を題材に使った問題は本当に多い。
もう出尽くしただろうと思いきやまた新たに出てくるので、
基本的な考え方は覚えておくと良さそうである。
過去のコンテストを参考にいくつか問題の考え方を覚え書きする。
１、基本
括弧を使った正しい文字列の定義は次のようなものが多い。
・空文字""は正しい文字列である。
・Aを正しい文字列とすると"(A)"は正しい文字列。
・A、Bをそれぞれ正しい文字列とすると"AB"は正しい文字列。
例えば、""、"()"、"(())"、"()()"、"(()(()))"は正しい文字列である。
簡単な条件として「文字列の長さは偶数」がある。
また、'('の数と')'の数は等しい。
２、カタラン数
単純に()がn組あるときの正しい組み合わせの数え上げはカタラン数に等しい。
カタラン数 C(n)=((2*n)!)/((n+1)!*n!)
例えば、n=3のときC(n)=5である。
これは"()()()"、"()(())"、"(()())"、"(())()"、"((()))"の5通りに等しい。
カタラン数は他に2*n人が輪になったとき交差せず手をつなぐ場合の数にも等しい。
３、括弧が正しい文字列になっているかの判定
最初0からはじめ文字列を左からを見ていき'('があれば1を加算し')'があれば1を減算する。
計算の途中で数値がマイナスになっていなくて最後の結果が0であれば正しい文字列である。
このように括弧で考えず数値で考えると考えやすい場合が多い。
計算量はO(N)。
int main() {
int flag = 1;
string s = "(()(()))";
int c = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]=='(')c++;
else c--;
if(c<0)flag = 0;
}
if(c==0&&flag==1){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
return 0;
}
４、問題１(SRM 521 Div1 Easy)
ある括弧文字'('と')'からなる文字列がある。
この文字列に括弧文字を挿入して正しい括弧文字を作る。
追加する最少の括弧文字の数を答えよ。
計算量はO(N)。
例えば、")(()"の場合、"()()()"や"()(())"のように２個追加すれば良い。
考え方は「追加する」を「実際に追加はせずに追加に対応する括弧を消す」と考える。
左から文字列を見ていき'('が出たら貯めておく、')'がきたら貯めておいた'('を使う。
')'が来たときに貯めておいた'('が無かったら消す。
また、最後に'('が余ったらすべて消す。
int main() {
int flag = 1;
string s = ")(()((())";
int ans = 0;
int c = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]=='(')c++;
else{
if(c>0)c--;
else ans++;
}
}
ans += c;
cout << ans << endl;
return 0;
}
５、問題２(SRM 714 Div1 Easy)
ある括弧文字'('と')'からなる正しい文字列がある。
左から見ていき'('があったら対応する')'を選んで両方を消す操作を繰り返す。
1つのペアを消したあとに残った文字列は常に正しい文字列でなければならない。
このような消し方は何通りあるか？
計算量はO(N)。
例えば、"(())"の場合、{0,2},{1,3}で消す方法と、{0,3},{1,2}で消す方法の2通りがある。
考え方は問題１とまったく逆。
前から考えるとどの'('と')'を対応させるべきかまったくわからないので後ろから考える。
後ろから考えると'('と対応するのはいままでに出てきた')'のいずれかとわかる。
文字列の後ろから')'を貯めていって'('が来たらいずれかの')'を割り当てる。
最初に与えられるのは正しい文字列なので')'が不足することはない。
int main() {
int flag = 1;
string s = "()()(()(()))";
int ans = 1;
int c = 0;
for(int i = s.size()-1; i >= 0; i--){
if(s[i]==')')c++;
else{
ans *= c;
c--;
}
}
cout << ans << endl;
return 0;
}
６、問題３
ある括弧文字'('と')'と文字'?'からなる文字列がある。
文字'?'を'('か')'のいずれかに置き換えて正しい文字列を作れ。
答えが複数ある場合はどれかひとつを出力すること。
なお、不可能な場合には文字列"Impossible"を出力すること。
計算量はO(N)。
例えば、"(??)"であれば、"()()"や"(())"が答えである。
また、")?)"であれば答えは"Impossible"である。
まず最終的に'('と')'の数は同じでなければならない。
次に、左から優先的に'('を使ったほうが良い。
よって、'('と')'と'?'の数を先に数えて、いくつの'?'を'('にすべきか計算する。
数がわかったら左から'('を割り当てていけば良い。残りは')'。
最後に、作った文字列が正しい文字列になっているかどうかのチェックが必要。
int main() {
string s = "(?()(?)?";
if(s.size()%2==1){
cout << "Impossible" << endl;
return 0;
}
int c = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]=='(')c++;
}
c = s.size()/2-c;
if(c<0){
cout << "Impossible" << endl;
return 0;
}
for(int i = 0; i < s.size(); i++){
if(s[i]=='?'){
if(c>0){
s[i] = '(';
c--;
}
else{
s[i] = ')';
}
}
}
int flag = 1;
for(int i = 0; i < s.size(); i++){
if(s[i]=='(')c++;
else c--;
if(c<0)flag = 0;
}
if(c==0&&flag==1){
cout << s << endl;
}
else{
cout << "Impossible" << endl;
}
return 0;
}
７、問題４
ある括弧文字'('と')'と文字'?'からなる文字列がある。
なお、特別ルールとして先に最後の連続した何文字かを好きなだけ捨てることが可能である。
文字'?'を'('か')'のいずれかに置き換えてできた最長の正しい文字列の長さはいくつか。
計算量はO(N)。
例えば、"(?)))("であれば、最後の")("を捨てて"(())"の4が答えである。
捨てる文字が最初に定まらないのでいくつ'?'を'('で埋めるかが決まらない。
２分探索でいけるように思うが"?((()))?"の場合のときなどに失敗する。
また、捨てる文字の数を総当たりする方法もO(N^2)になってしまう。
考え方は、先頭から数値0を1加算もしくは1減算していく方法を考える。
'('が来たときには1を加算、')'が来たときには1を減算する。
'?'が来たときには1を加算ないし、1を減算してありうる最大値と最小値を更新する。
この更新の際に最大値、最小値がマイナスになってはいけない。
左から見ていって最小値が0である場合の文字列の長さの最大が答え。
int main() {
string s = "(?)))(";
int ans = 0;
int mx = 0;
int mn = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]=='('){
mx++;
mn++;
}
else if(s[i]==')'){
mx--;
mn--;
}
else{
mx++;
mn--;
}
if(mx<0)break;
if(mn<0)mn=1;
if(mn==0){
ans = i+1;
}
}
cout << ans << endl;
return 0;
}
８、問題５
ある括弧文字'('と')'からなる文字列がある。
先頭からl番目の文字からr番目の文字までの連続した文字列が正しい場合が何通りあるか数えよ。
計算量はO(N)。
考え方、左から高さが同じになる場合を数えていけば良い。
ただし、高さがマイナスになる場合を数えてはいけないので、
高さがマイナスになる場合の高さの場合は0でクリアしなければならない。
long long d[200100];
int main(void) {
string s;
cin>>s;
long long ans = 0;
long long p = 100050;
for(long long i = 0; i < s.sz; i++){
if(s[i]=='('){
d[p]++;
p++;
}
else{
d[p]=0;
p--;
ans += d[p];
}
}
cout << ans << endl;
return 0;
}
９、問題６
ある括弧文字'('と')'からなる文字列がある。
先頭からl番目の文字からr番目の文字までの連続した文字列が正しいか判定せよ。
準備O(NlogN)、計算量はO(logN)。
例えば、"()()"であれば{0,1}は正しい、{1,2}は正しくない。
考え方、ある区間の文字列が正しい文字列かどうかはセグメント木で判定できる。
左から'('がくると高さが1上がる、')'がくると高さが1下がると考える。
lとrの両端の高さを調べて同じであること、またその間の高さの最小値が両端を下回らないこと。
以上を調べれば良い。
#define N_MAX (1<<20)
#define INF 1000000000000000000LL
struct segmn{
long long nn;
long long dat[(2 * N_MAX) - 1];
void init(long long n1){
nn = 1;
while(nn < n1)nn *= 2;
for(long long i = 0; i < 2 * nn - 1; i++){
dat[i] = INF;
}
}
void update(long long k, long long a){
k += nn - 1;
dat[k] = a;
while(k > 0){
k = (k - 1) / 2;
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
long long query(long long a, long long b, long long k, long long l, long long r){
if(r <= a || b <= l)return INF;
if(a <= l && r <= b){
return dat[k];
}
else{
long long vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
long long vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
long long query(long long a, long long b){
return query(a,b,0,0,nn);
}
}segmn1;
int main() {
string s = "()()";
segmn1.init(s.size()+1);
segmn1.update(0,0);
int c = 0;
for(int i = 0; i < s.size(); i++){
if(s[i]=='('){
c++;
}
else{
c--;
}
segmn1.update(i+1,c);
}
int l = 0;
int r = 1;
int hl = segmn1.query(l,l+1);
int hr = segmn1.query(r+1,r+2);
if(hl==hr&&hl<=segmn1.query(l,r+2)){
cout << "Yes" << endl;
}
else{
cout << "No" << endl;
}
return 0;
}
１０、問題７
ある括弧文字'('と')'からなる文字列がある。
部分文字列として正しい文字列はいくつあるか？
計算量はO(N^2)。
例えば、"((()"であれば3つ、"(())"であれば5つ。
現在何文字めかと高さを持つ動的計画法が使える。
制約から動的計画法を使えそうなら使っておくのがいちばん安全かも。
ちなみに「連続する部分文字列」であればi文字めから右へ調べる方法でO(N^2)でできる。
int dp[21][21];
int main() {
string s = "(())";
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
for(int i = 1; i < s.size()+1; i++){
for(int j = 0; j < s.size(); j++){
dp[i][j] += dp[i-1][j];
if(s[i-1]=='('){
dp[i][j+1] += dp[i-1][j];
}
else{
if(j>0)dp[i][j-1] += dp[i-1][j];
}
}
}
cout << dp[s.size()][0]-1 << endl;
return 0;
}
