Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM 371 RaceOrdering

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

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

  • グラフで考えればいい気がする
    • 制約条件のある頂点をグループ分けして、そのグループの配置位置をnCrしようとした

後で

  • ↑の方針で解いた。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RaceOrdering {
	int MOD = 1000003;
	int n;
	boolean[][] graph;
	boolean[] done;
	long[][] memo;
	long[][] ncr;
	List<Integer> res;
	
	public void dfs(int i) {
		if (done[i]) {
			return;
		}
		done[i] = true;
		res.add(i);
		for (int j = 0 ; j < n ; j++) {
			if (graph[i][j] || graph[j][i]) {
				dfs(j);
			}
		}
	}
	
	public long count(int left) {
		int rlen = res.size();
		int[] idx = new int[rlen];
		for (int i = 0 ; i < rlen ; i++) {
			idx[i] = res.get(i);
		}
		
		long[] dp = new long[1<<rlen];
		dp[0] = 1;
		for (int ptn = 0 ; ptn < (1<<rlen) ; ptn++) {
			if (dp[ptn] == 0) {
				continue;
			}
			for (int next = 0 ; next < rlen ; next++) {
				if ((ptn & (1<<next)) >= 1) {
					continue;
				}
				int tidx = idx[next];
				int nptn = ptn | (1<<next);
				boolean isok = true;
				for (int prv = 0 ; prv < rlen ; prv++) {
					int fidx = idx[prv];
					if (graph[fidx][tidx] && (ptn & (1<<prv)) == 0) {
						isok = false;
						break;
					}
				}
				if (isok) {
					dp[nptn] += dp[ptn];
					dp[nptn] %= MOD;
				}
			}
		}
		return (dp[(1<<rlen)-1] * ncr[left][rlen]) % MOD;
	}
	
	
	public int countOrders(int _n, int[] first, int[] second) {
		n = _n;
		int len = first.length;
		ncr = new long[41][41];
		for (int i = 0 ; i < 41 ; i++) {
			ncr[i][0] = 1;
			ncr[i][i] = 1;
			for (int j = 1 ; j < i ; j++) {
				ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1]) % MOD;
			}
		}
		
		graph = new boolean[n][n];
		for (int i = 0 ; i < len ; i++) {
			graph[first[i]][second[i]] = true;
		}
		
		for (int k = 0 ; k < n ; k++) {
			for (int i = 0 ; i < n ; i++) {
				for (int j = 0 ; j < n ; j++) {
					if (graph[i][k] && graph[k][j]) {
						graph[i][j] = true;
					}
				}
			}
		}
		for (int i = 0 ; i < n ; i++) {
			if (graph[i][i]) {
				return 0;
			}
		}
		done = new boolean[n];
		long ans = 1;
		int left = n;
		for (int i = 0 ; i < n ; i++) {
			if (!done[i]) {
				res = new ArrayList<Integer>();
				dfs(i);
				ans *= count(left);
				ans %= MOD;
				left -= res.size();
			}
		}
		return (int)ans;
	}
}