Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-27SRM358 (Practice)

SRM 358 BalanceScale

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

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

  • 複数の数のgcdを取った時、1にする最小の個数を求める
    • 練習ではなぜか最小費用流を適用しようとしてハマる
  • シンプルなBFSで十分間に合う。
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;


public class BalanceScale {

	public int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a%b);
	}
	
	public int[] facts(int n) {
		Set<Integer> p = new HashSet<Integer>();
		int nn = n;
		for (int i = 2 ; i * i <= n ; i++) {
			if (n % i == 0) {
				p.add(i);
				while (n % i == 0){
					n /= i;
				}
			}
		}
		
		int[] ret = new int[p.size()];
		int idx = 0;
		for (int pp : p) {
			ret[idx] = pp;
			idx++;
		}
		return ret;
	}
	
	public int takeWeights(int[] weight) {
		int len = weight.length;
		int gcd = weight[0];
		for (int i = 1 ; i < len ; i++) {
			gcd = gcd(gcd, weight[i]);
		}
		for (int i = 0 ; i < len ; i++) {
			weight[i] /= gcd;
			if (weight[i] == 1) {
				return 1;
			}
		}
		
		char[] dp = new char[10000001];
		Arrays.fill(dp, (char)127);
		Queue<Integer> q = new PriorityQueue<Integer>(100001);
		for (int i = 0 ; i < len ; i++) {
			dp[weight[i]] = 1;
			q.add(weight[i]);
		}
		while (q.size() >= 1) {
			int stat = q.poll();
			for (int k = 0 ; k < len ; k++) {
				int togcd = gcd(stat, weight[k]);
				if (dp[togcd] > dp[stat] + 1) {
					dp[togcd] = (char)(dp[stat] + 1);
					q.add(togcd);
				}
			}
		}
		return dp[1];
	}
}