Div1より簡単だった。
https://community.topcoder.com/stat?c=problem_statement&pm=14211
問題
括弧からなる文字列が与えられる。
この部分文字列として正しい括弧列は何通り作れるか。
なお、Div1と異なり、抜き出した場所が異なっても得られる部分文字列が等しいなら1つと見なす。
解法
部分文字列の数え上げは最近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の問題とこの問題で、部分文字列の数え上げは少し身についたかな。