TopCoder SRM 520 Div1 Medium: SRMIntermissionPhase

解法

d.hatena.ne.jp

DPする。総和をとるところで式を工夫して、問題数の少ない方から埋めていくとO(MAX_P)で計算することができる。

コード

public class SRMIntermissionPhase {
	private final long MOD = (int) 1e9 + 7;

	public int countWays(int[] points, String[] description) {
		int N = description.length;
		int MAX_P = points[0] + points[1] + points[2];

		int[] states = new int[N];
		for (int i = 0; i < N; i++) {
			int bit = 0;
			for (int j = 0; j < 3; j++) {
				if (description[i].charAt(j) == 'Y') {
					bit |= 1 << j;
				}
			}
			states[i] = bit;
		}

		// ways[bit][point]:= bitの状態でpointとる方法
		long[][] ways = new long[1 << 3][MAX_P + 1];

		ways[0][0] = 1;
		for (int bit = 1; bit < 8; bit++) {
			int left = 2;
			while (((bit >> left) & 1) == 0) {
				left--;
			}

			// leftを解く前のbit
			int prevBit = bit ^ (1 << left);

			// 累積和っぽい感じで計算量を減らす
			for (int point = 1; point <= MAX_P; point++) {
				ways[bit][point] = ways[bit][point - 1];
				ways[bit][point] += ways[prevBit][point - 1];

				// [prevBit][lowest-1]->[bit][point]は遷移し得ないので引いておく
				int lowest = point - points[left];
				if (lowest > 0) {
					ways[bit][point] -= ways[prevBit][lowest - 1];
				}
			}
		}

		long[] from = ways[states[0]];
		for (int i = 1; i < N; i++) {
			long[] next = new long[MAX_P + 1];

			// 遷移させる
			long sum = 0;
			for (int point = MAX_P; point >= 0; point--) {
				next[point] = sum * ways[states[i]][point] % MOD;
				sum = (sum + from[point]) % MOD;
			}
			from = next;
		}

		long ans = 0;
		for (int i = 0; i <= MAX_P; i++) {
			ans = (ans + from[i]) % MOD;
		}

		return (int) ans;
	}
}