Topcoder SRM 714 Div.1 Easy - ParenthesisRemoval
問題概要
開き括弧と閉じ括弧のみからなる文字列Sが与えられる。初めSの括弧は正しく対応している。Sの一番前にある開き括弧と任意の閉じ括弧のペアを括弧の対応が不正にならないよう取り除く、という操作をSが空になるまで繰り返すとき、括弧の選び方の順番が何通りあるか答えよ。すべての括弧は一番最初のインデックスによって区別されるものとする。
|S| <= 2500
解法
閉じ括弧の側から考える。Sを前から見ていって最初の閉じ括弧に当たったとき、その閉じ括弧と一緒に消せる可能性があるのはそれより前にある開き括弧だけである。よって以下の手順で計算を行える。Sを前から見ていき、その文字が開き括弧ならカウンターを1増やす、閉じ括弧ならばカウンターを1減らす。閉じ括弧に当たった時点でのカウンターの数を掛け合わせたものが答え。O(|S|)
感想
視点を変えると一瞬で答えが出て面白かった
コード (C++)
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; const ll MOD = 1000000007; class ParenthesisRemoval { public: int countWays(string s) { int N = s.length(); ll ans = 1; ll open = 0; REP(i, N) { if (s[i] == '(') { open += 1; } else { ans = ans * open % MOD; open -= 1; } } return (int)ans; } };