Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-02SRM353, SRM354 (Practice)

SRM 354 RooksPlacement

|  SRM 354 RooksPlacement - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 354 RooksPlacement - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7658

  • シンプルなDPのはずだがなかなか答えが合わず。
    • 考えてる状態数が足りないことに時間切れ直前になって気づいた
  • 通した。
    • 考察が足りなかった
public class RooksPlacement {
	long MOD = 1000001;
	int n, m, k;
	int K;
	long[][][] memo;
	long[][] ncr;
	
	public long ncr(int a, int b) {
		if (b > a) {
			return 0;
		}
		if (a <= 0) {
			return 0;
		}
		return ncr[a][b];
	}
	
	public long dfs(int now, int cv1, int cv2) {
		int left = k - cv1 - cv2; 
		if (now == n) {
			if (left == 0) {
				return 1;
			}
			return 0;
		} else if (now > n) {
			return 0;
		}
		if (memo[now][cv1][cv2] >= 0) {
			return memo[now][cv1][cv2];
		}
		if (left <= -1) {
			return 0;
		}

		long ret = 0;
		int free0 = m - cv1;
		
		// place two
		{
			long f02 = ncr(free0, 2);
			if (f02 >= 1) {
				ret += dfs(now+1, cv1+2, cv2) * f02;
				ret %= MOD;
			}
		}

		// place one
		{
			if (free0 >= 1) {
				ret += dfs(now+1, cv1+1, cv2) * free0;
				ret %= MOD;
			}
			
			long r2 = ncr(n - now - 1, 1);
			if (r2 >= 1 && free0 >= 1) {
				ret += dfs(now+2, cv1+1, cv2+1) * r2 * free0;
				ret %= MOD;
			}
		}
		
		// dont place
		ret += dfs(now+1, cv1, cv2);
		
		memo[now][cv1][cv2] = ret;
		return ret;
	}
	
	public int countPlacements(int N, int M, int K) {
		n = N;
		m = M;
		k = K;
		memo = new long[101][101][101];
		for (int i = 0 ; i < 101 ; i++) {
			for (int j = 0 ; j < 101 ; j++) {
				for (int k = 0 ; k < 101 ; k++) {
					memo[i][j][k] = -1;
				}
			}
		}
		ncr = new long[201][201];
		for (int i = 0 ; i < 201 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % MOD;
			}
		}
		
		return (int)(dfs(0, 0, 0) % MOD);
	}
}