SRM 714 div 1 easy : ParenthesisRemoval
問題概要 :
正しい対応関係を持つ括弧の文字列が与えられる
その文字列の先頭の開き括弧 ( とそれより後ろにあるいずれかの閉じ括弧 ) を削除する
削除後の文字列の括弧の対応関係も正しくなければならない
このとき、括弧の消し方は何通りあるか?
解法:
後ろから数え上げる
文字列を後ろから見ていき、 開き括弧がきたら
それより後ろの閉じ括弧の数 - それより後ろの開き括弧の数 # コメント : これはいま見ている開き括弧と一緒に消すことができる括弧の数
を答えにどんどんかけていく
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) #define EPS 1e-10 #define equals(a,b) (fabs((a)-(b)) < EPS) using namespace std; typedef long long ll; const int IINF = INT_MAX; const ll mod = 1000000007; class ParenthesisRemoval { public: int countWays(string s) { ll ans = 1; int L = 0, R = 0; for(int i=(int)s.size()-1;i>=0;--i) { if( s[i] == ')' ) ++R; else { ans = ( ans * ( R - L ) ) % mod; ++L; } } return ans; } };