読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

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;
  }
};