Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-03SRM350, SRM351, SRM352 (Practice)

SRM 350 StarsInGraphs

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

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

  • まず、全頂点のstar numberを求める。
  • 「今どこにいるか」を状態としたダイクストラをする
    • 経由頂点数が100を超えるようだったらループしてるので、-1を返す。
  • 練習ではDPの更新部分でバグっててWAした。
import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class StarsInGraphs {
	class State {
		int now;
		int prev;
		int cnt;
		State(int n, int p, int c) {
			now = n;
			prev = p;
			cnt = c;
		}
	}
	
	int len;
	boolean[][] graph;
	boolean[] done;
	long[] star;
	
	public int starryPaths(String[] adj, int C) {
		len = adj.length;
		graph = new boolean[len][len];
		int[] deg = new int[len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				graph[i][j] = (adj[i].charAt(j) == '1');
				if (graph[i][j]) {
					deg[i]++;
				}
			}
		}
		
		
		long[][] ncr = new long[51][51];
		for (int i = 0 ; i < 51 ; 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];
			}
		}
		
		
		star = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			long s = 0;
			for (int d = 3 ; d <= deg[i] ; d++) {
				s += ncr[deg[i]][d];
				if (s <= -1) {
					s = -1;
					break;
				} else if (s > C) {
					s = -1;
					break;
				}
			}
			if (1 <= s && s <= C) {
				star[i] = s;
			} else {
				star[i] = -1;
			}
		}
		
		Queue<State> q = new PriorityQueue<State>(10000, new Comparator<State>(){
			public int compare(State o1, State o2) {
				return o2.cnt - o1.cnt;
			}
		});
		int[] dp = new int[len];
		for (int i = 0 ; i < len ; i++) {
			if (star[i] >= 1) {
				dp[i] = 1;
				q.add(new State(i, i, 1));
			}
		}
		
		int max = 0;
		while (q.size() >= 1) {
			State s = q.poll();
			max = Math.max(max, s.cnt);
			for (int i = 0 ; i < len ; i++) {
				if (i != s.prev && graph[s.now][i] && star[i] >= star[s.now]) {
					if (dp[i] < s.cnt + 1) {
						dp[i] = s.cnt + 1;
						if (dp[s.now] >= 100) {
							return -1;
						}
						q.add(new State(i, i, s.cnt + 1));
					}
				}
			}
		}
		return max;
	}
}