TopCoder SRM 714 Div1 Easy ParenthesisRemoval、Div2 Medium RemovingParenthesis

ギリギリMediumを通してレート増。
https://community.topcoder.com/stat?c=problem_statement&pm=14595
https://community.topcoder.com/stat?c=problem_statement&pm=14593

問題

正しい括弧列(詳細な定義は問題文参照)を成す文字列が与えられる。
この文字列に対し、最も手前にある開き括弧と、任意の閉じ括弧を選び、両者を消すという処理を繰り返す。
その過程で文字列が常に正しいような括弧の組み合わせの選び方は何通りか。

解法

手前から選んでいくと難しい。
途中、よくない閉じ括弧とペアにしてしまうと、正しい括弧列にならなくなってしまうためである。

なお、正しい括弧列の定義のうち、このよくないペアで生じるのは途中開き括弧と対応しない閉じ括弧が生じることである。
逆に、そのような括弧が登場しないようペアを組めばよい。

そこで、発想を変えて後ろの開き括弧から対応する閉じ括弧を割り当てよう。
括弧列が正しいなら、開き括弧の後に登場する閉じ括弧の数は、必ず後者の方が多いため、あとで不整合となることはない。
そう考えると、文字列を後ろから見ていき、ペアを組んでいない閉じ括弧の数を数えて掛け合わせていくだけでよい。

class ParenthesisRemoval {
	public:
	int countWays(string s) {
		ll mo=1000000007;
		ll ret=1;
		int left=0;
		
		for(int i=s.size()-1;i>=0;i--) {
			if(s[i]==')') left++;
			else ret=ret*left%mo, left--;
		}
		
		return ret;
		
	}
}

まとめ

O(|S|^2)解法も通るけど。