TopCoder SRM 671 Div1 Easy BearCries

せっかくMedium解いたのに、Easyのしょうもないミスでレート減。
http://community.topcoder.com/stat?c=problem_statement&pm=14010

問題

泣き顔の顔文字とは、2つのセミコロンの間に1つ以上アンダースコアがある";_;"や";___;"のような文字列をいう。

N文字の文字列Sが与えられる。
これを(不連続でも良い)複数の泣き顔の文字列に分割したい。
分割後の文字列が同一でも、元の文字列から抜き出した位置が異なる場合は別の抜き出し方とカウントするとき、条件を満たす分割方法は何通りあるか。

解法

(こちらから見て)左の目を顔文字が開く、右の目を顔文字が閉じると表現する。
顔文字が閉じるには、開いたのち閉じるまでに最低1つのアンダースコアを含まなければならない。
言い換えると、文字列を順に1文字ずつ処理していく際、開いている顔文字に対し1個以上アンダースコアを含むかどうかを区別して覚えておく必要がある。

よって、
dp[文字の位置][まだアンダースコアを含まない開いた顔文字数][既に1個以上アンダースコアを含む開いた顔文字数] := 状態を満たす組み合わせ数
としてO(N^3)のDPをしていけば良い。

ll mo=1000000007;

ll dp[204][102][103];

class BearCries {
	public:
	int count(string M) {
		int L=M.size(),i,x,y,z;
		ZERO(dp);
		
		dp[0][0][0]=1;
		FOR(i,L) {
			for(x=0;x<101;x++) FOR(y,101) if(dp[i][y][x]) {
				ll d=dp[i][y][x];
				if(M[i]=='_') {
					if(y) (dp[i+1][y-1][x+1] += d*y)%=mo;
					if(x) (dp[i+1][y][x] += d*x)%=mo;
				}
				else {
					if(x) (dp[i+1][y][x-1] += d*x)%=mo;
					(dp[i+1][y+1][x] += d)%=mo;
				}
			}
		}
		return dp[L][0][0];
		
	}
}

まとめ

配列サイズを間違えるという初歩的なミスをやらかした。