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

TopCoder SRM 528 Div1 Medium: SPartition

競技プログラミング SRM

解法

作られる文字列は 2^{20}種類のうち条件を満たすものだけなので大して種類はない.
ある文字列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;
	}

}