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]; } }