Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-27SRM358 (Practice)

問題結果ポイントその他
250BrokenButtonsAccepted224.56ブルートフォース
500BalanceScaleOpened0.00数論、BFS
1000SharksDinnerUnopened0.00最大流

SRM 358 BrokenButtons

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

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

  • 制約が緩いので全部試しても間に合う。
public class BrokenButtons {

	public int minPresses(int page, int[] broken) {
		int min = Math.abs(page - 100);
		boolean[] cantuse = new boolean[10];
		for (int b : broken) {
			cantuse[b] = true;
		}
		for (int d = -2000000 ; d <= 2000000 ; d++) {
			int go = page + d;
			if (go < 0) {
				continue;
			}
			boolean isok = true;
			int cnt = 0;
			if (go == 0) {
				isok = (!cantuse[0]);
				cnt = 1;
			} else {
				while (go >= 1) {
					int m10 = go % 10;
					if (cantuse[m10]) {
						isok = false;
						break;
					}
					go /= 10;
					cnt++;
				}
			}
			if (isok) {
				min = Math.min(min, Math.abs(d) + cnt);
			}
		}
		
		return min;
	}

}

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];
	}
}

SRM 358 SharksDinner

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

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

  • こっちは最大流。
    • 各ノードを食べる側1、食べる側2、食われる側の3つに分割すると2部グラフになる
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SharksDinner {
	public class Edge {
		int to;
		int cap;
		int rev;
		public Edge(int _to, int _cap, int _rev) {
			to = _to;
			cap = _cap;
			rev = _rev;
		}
	}
	public Map<Integer, List<Edge>> graph = new HashMap<Integer, List<Edge>>();
	public boolean[] used;
	public void init(int size) {
		for (int i = 0 ; i < size ; i++) {
			graph.put(i, new ArrayList<Edge>());
		}
		used = new boolean[size];
	}
	public void edge(int from, int to, int cap) {
		graph.get(from).add(new Edge(to, cap, graph.get(to).size()));
		graph.get(to).add(new Edge(from, 0, graph.get(from).size() - 1));
	}
	public int dfs(int v, int t, int f) {
		if (v == t) return f;
		used[v] = true;
		for (int i = 0 ; i < graph.get(v).size() ; i++) {
			Edge e = graph.get(v).get(i);
			if (!used[e.to] && e.cap > 0) {
				int d = dfs(e.to, t, Math.min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					graph.get(e.to).get(e.rev).cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	public int max_flow(int s, int t) {
		int flow = 0;
		while (true) {
			used = new boolean[graph.size()];
			int f = dfs(s, t, Integer.MAX_VALUE);
			if (f == 0) {
				break;
			}
			flow += f;
		}
		return flow;
	}

	public int minSurvivors(int[] size, int[] speed, int[] intel) {
		int len = size.length;
		boolean[][] graph = new boolean[len][len];
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (i == j) {
					continue;
				}
				if (size[i] >= size[j] && speed[i] >= speed[j] && intel[i] >= intel[j]) {
					graph[i][j] = true;
				}
			}
		}
		
		int start = len * 3;
		int goal = start + 1;
		int eaten = len * 2;
		
		init(goal+1);
		for (int i = 0 ; i < len ; i++) {
			edge(start, i*2, 1);
			edge(start, i*2+1, 1);
			edge(eaten+i, goal, 1);
		}
		
		for (int i = 0 ; i < len ; i++) {
			for (int j = 0 ; j < len ; j++) {
				if (graph[i][j]) {
					if (size[i] == size[j] && speed[i] == speed[j] && intel[i] == intel[j]) {
						if (i < j) {
							edge(i*2, eaten+j, 1);
							edge(i*2+1, eaten+j, 1);							
						}
					} else {
						edge(i*2, eaten+j, 1);
						edge(i*2+1, eaten+j, 1);
					}
				}
			}
		}
		return len - max_flow(start, goal);
	}
}