TopCoder SRM 528 Div1 Medium: SPartition

解法

作られる文字列は種類のうち条件を満たすものだけなので大して種類はない．
ある文字列maskを作る時，stringを前から見ていき，Xに入れられるか，あるいは，Yに入れられるかというのでdpを遷移させていけばいい．

コード

public class SPartition {
	public long getCount(String s) {
		// 'x'の数を数える
		int x = 0;
		for (int i = 0; i < s.length(); i++)
			if (s.charAt(i) == 'x')
				x++;

		// 'x'の数が奇数なら無理
		if (x % 2 == 1) {
			return 0;
		}

		char[] str = s.toCharArray();
		int N = s.length() / 2;

		long res = 0;

		for (int bitmask = 0; bitmask < (1 << N); bitmask++) {
			if (Integer.bitCount(bitmask) != x / 2) {
				continue;
			}

			// maskの状態をnowに入れる
			char[] mask = new char[N];
			for (int i = 0; i < N; i++) {
				if ((bitmask & (1 << i)) != 0) {
					mask[i] = 'x';
				} else {
					mask[i] = 'o';
				}
			}

			if (mask[0] != str[0]) {
				continue;
			}

			long[][] dp = new long[2 * N][N];
			dp[0][0] = 1;

			for (int pos = 1; pos < N * 2; pos++) {
				for (int j = Math.max(pos - N, 0); j <= pos && j < N; j++) {
					// Xの作り方
					if (str[pos] == mask[j] && j != 0) {
						dp[pos][j] += dp[pos - 1][j - 1];
					}

					// Yの作り方
					if (pos != j && str[pos] == mask[pos - j - 1]) {
						dp[pos][j] += dp[pos - 1][j];
					}
				}
			}

			res += dp[2 * N - 1][N - 1];
		}

		return res * 2;
	}

}