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

TopCoder SRM 671 Div1 Easy: BearCries

解法

まだ顔として使われていない;の数と;_の数を保持したDPをすれば良い。

コード

public class BearCries {

    private final int MOD = (int) 1e9 + 7;

    public int count(String string) {
	int N = string.length();
	char[] m = string.toCharArray();

	// i文字目まで見た時の, 使ってない;_の数がj個あり, 使ってない;の数がk個ある時の顔の作り方のパターン数
	long[][][] dp = new long[N + 1][N + 1][N + 1];
	dp[0][0][0] = 1;
	for (int i = 0; i < N; i++) {
	    for (int j = 0; j <= i; j++) {
		for (int k = 0; k <= i; k++) {
		    if (dp[i][j][k] == 0) {
			continue;
		    }

		    if (m[i] == ';') {
			// ;をチャージして次の文字に進む
			dp[i + 1][j][k + 1] += dp[i][j][k];
			dp[i + 1][j][k + 1] %= MOD;

			// j個の;_のうちどれかを選んで;_;にすることも出来る
			if (j > 0) {
			    dp[i + 1][j - 1][k] += dp[i][j][k] * j;
			    dp[i + 1][j - 1][k] %= MOD;
			}
		    } else {
			// '_'の時

			// k個の;のうち1つを消費して;_を作ることが出来る
			if (k > 0) {
			    dp[i + 1][j + 1][k - 1] += dp[i][j][k] * k;
			    dp[i + 1][j + 1][k - 1] %= MOD;
			}

			// j個の;_のうちのどれかに含めることで、jを維持したまま次の文字に行くことも出来る
			dp[i + 1][j][k] += dp[i][j][k] * j;
			dp[i + 1][j][k] %= MOD;
		    }
		}
	    }
	}

	return (int) dp[N][0][0];
    }

}