TopCoder SRM 686 Div2 Hard BracketSequenceDiv2

Div1より簡単だった。
https://community.topcoder.com/stat?c=problem_statement&pm=14211

問題

括弧からなる文字列が与えられる。
この部分文字列として正しい括弧列は何通り作れるか。

なお、Div1と異なり、抜き出した場所が異なっても得られる部分文字列が等しいなら１つと見なす。

解法

部分文字列の数え上げは最近Codeforcesで出た。
CROC 2016 Elimination Round : E. Intellectual Inquiry - kmjp's blog
あとはこれに加え、処理過程における開き括弧の超過数を同時に数えていけば良い。

ll dp[105][105];
int nex[105][2];
ll mo=1000000007;

class BracketSequenceDiv2 {
	public:
	int count(string s) {
		int i,j;
		int N=s.size();
		int p[2]={N+1,N+1};
		for(i=N;i>=0;i--) {
			nex[i][0]=p[0];
			nex[i][1]=p[1];
			if(i) p[s[i-1]==')']=i;
		}
		
		ll ret=0;
		ZERO(dp);
		dp[0][0]=1;
		FOR(i,N+1) {
			FOR(j,N+1) if(dp[i][j]) {
				if(i&&j==0) ret+=dp[i][j];
				(dp[nex[i][0]][j+1] += dp[i][j])%=mo;
				if(j) (dp[nex[i][1]][j-1] += dp[i][j])%=mo;
			}
		}
		
		return ret%mo;
		
	}
}

まとめ

CFの問題とこの問題で、部分文字列の数え上げは少し身についたかな。