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

TopCoder SRM 532 Div1 Medium: DengklekBuildingRoads

SRM 競技プログラミング

解法

bitDP
tanzaku先生のコードを参考にした.

コード

public class DengklekBuildingRoads {
	private long MOD = (int) 1e9 + 7;
	private int K;
	private boolean[][][][] done;
	private long[][][][] dp;

	// nowを見た時に,残りedgeの辺が残っていて,start個以上離れた頂点から辺をnowに引いてくる場合の組み合わせの数
	// maskは直前k個と自分の次数の偶奇の状態
	private int bitDP(int now, int edge, int start, int mask) {
		if (edge == 0) { return mask == 0 ? 1 : 0; }
		if (now < 0) { return 0; }
		if (done[now][edge][start][mask]) { return (int) dp[now][edge][start][mask]; }

		long ans = 0;
		if ((mask & 1) == 0) ans += bitDP(now - 1, edge, 1, mask >> 1);

		for (int k = start; k <= K; k++) {
			if (k > now) break;// nowがまだ小さい時

			int nextbit = mask;
			nextbit ^= (1 << 0);// 自分の分
			nextbit ^= (1 << k);// k個離れた頂点の分

			ans += bitDP(now, edge - 1, k, nextbit);
		}
		done[now][edge][start][mask] = true;
		dp[now][edge][start][mask] = ans % MOD;
		return (int) dp[now][edge][start][mask];
	}

	public int numWays(int N, int M, int K) {
		this.K = K;
		done = new boolean[N][M + 1][K + 1][1 << (K + 1)];
		dp = new long[N][M + 1][K + 1][1 << (K + 1)];
		return bitDP(N - 1, M, 1, 0);
	}
}

理解するのにすごく時間がかかってしまった.