Google Code Jam 2013 Round 1A

Round 1Aがありました。
上位陣のソースを見て復習しました。

Problem A. Bullseye

二分探索の問題。 i番目（i=1,2,...）の黒い円の面積は、Si = (2 * r + (4 * i - 3))πと表すことが出きるので、円をN個塗った場合の面積の合計値は、ΣSi = (2 * N² + (2 * r - 1) * N)πとなる。 Nが決まれば面積が決まり、塗料が足りているのかどうかはO(1)で判定できる。よってNを二分探索で決めればいい。

	import static java.lang.Math.*;
	import static java.util.Arrays.*;
	import static java.math.BigInteger.*;
	import java.io.*;
	import java.util.*;
	@SuppressWarnings("unused")
	public class A {
	Scanner sc = new Scanner(System.in);
	void solve() {
	long r = sc.nextLong();
	long t = sc.nextLong();
	long lo = 1;
	long hi = (long) 1e9 + 10;
	while (hi - lo > 1) {
	long x = (lo + hi) / 2;
	if (2.0 * x * x + (2.0 * r - 1) * x > 1.1 * t)
	hi = x;
	else if (2 * x * x + (2 * r - 1) * x > t)
	hi = x;
	else
	lo = x;
	}
	System.out.println(lo);
	}
	void run() {
	int caseN = sc.nextInt();
	for (int caseID = 1; caseID <= caseN; caseID++) {
	System.out.printf("Case #%d: ", caseID);
	System.err.printf("Solving Case #%d...\n", caseID);
	solve();
	System.out.flush();
	}
	}
	void debug(Object... os) {
	System.err.println(deepToString(os));
	}
	public static void main(String[] args) {
	new A().run();
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Problem B. Manage your Energy

動的計画法で解く。今i番目までのタスクが最適にこなされているとする。
そこに(i+1)番目のタスクを加えたときに、i番目までの解を後ろから走査していきより（i+1）番目のタスクに多くのエネルギーを使った方がいいのかどうかを見ていけばいい。

	import static java.lang.Math.*;
	import static java.util.Arrays.*;
	import static java.math.BigInteger.*;
	import java.io.*;
	import java.util.*;
	@SuppressWarnings("unused")
	public class B {
	Scanner sc = new Scanner(System.in);
	void solve() {
	int E = sc.nextInt();
	int R = sc.nextInt();
	int N = sc.nextInt();
	int[] v = new int[N];
	for (int i = 0; i < N; i++)
	v[i] = sc.nextInt();
	if (R > E)
	R = E;
	long[] dp = new long[N];
	dp[0] = E;
	for (int i = 1; i < N; i++) {
	dp[i] = R;
	for (int j = i-1; j >= 0; j--) {
	if (v[j] >= v[i])
	break;
	if (dp[i] + dp[j] <= E) {
	dp[i] += dp[j];
	dp[j] = 0;
	} else {
	dp[j] -= E - dp[i];
	dp[i] = E;
	}
	}
	}
	long ret = 0;
	for (int i = 0; i < N; i++)
	ret += dp[i] * v[i];
	System.out.println(ret);
	}
	void run() {
	int caseN = sc.nextInt();
	for (int caseID = 1; caseID <= caseN; caseID++) {
	System.out.printf("Case #%d: ", caseID);
	System.err.printf("Solving Case #%d...\n", caseID);
	solve();
	System.out.flush();
	}
	}
	void debug(Object... os) {
	System.err.println(deepToString(os));
	}
	public static void main(String[] args) {
	new B().run();
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Problem C. Good Luck

確率の問題。観測される積の列がprとなる確率をp(pr)とおく。選ばれたカードの集合がxとなる確率をp(x)とおく。事後確率p(x | pr) = p(pr ∧ x) / p (pr)が最大となるようなxを出力すればいい。p(pr)はxによらず一意なので、p(pr ∧ x)が最大となるようなxを計算する。計算量を減らすためにxのpermutationは考えずに、xが非減少列となるようなものだけを考えて、確率を計算するときにpermutationを数えてあげるといい。

	import static java.lang.Math.*;
	import static java.util.Arrays.*;
	import static java.math.BigInteger.*;
	import java.io.*;
	import java.util.*;
	@SuppressWarnings("unused")
	public class C {
	Scanner sc = new Scanner(System.in);
	int R, N, M, K;
	List<Long> digits = new ArrayList<Long>();
	List<Long> ptrCnt = new ArrayList<Long>();
	List<Map<Long, Integer>> products
	= new ArrayList<Map<Long, Integer>>();
	long[] fact = new long[16];
	long toLong(int[] a) {
	long ret = 0;
	for (int i = 0; i < a.length; i++)
	ret = 10 * ret + a[i];
	return ret;
	}
	void dfs(int p, int[] a) {
	if (p == N) {
	// add obtained digits
	digits.add(toLong(a));
	// add the number of permutation of the digits
	long perm = fact[N];
	for (int i = 2; i <= M; i++) {
	int cnt = 0;
	for (int j = 0; j < N; j++)
	if (a[j] == i)
	++cnt;
	perm /= fact[cnt];
	}
	ptrCnt.add(perm);
	// add the possible products and their frequencies
	HashMap<Long, Integer> pr = new HashMap<Long, Integer>();
	for (int k = 0; k < 1<<N; k++) {
	long x = 1;
	for (int i = 0; i < N; i++)
	if ((k & 1 << i) > 0)
	x *= a[i];
	int tmp = pr.containsKey(x) ? pr.get(x) : 0;
	pr.put(x, ++tmp);
	}
	products.add(pr);
	}
	else {
	for (int i = (p == 0) ? 2 : a[p-1]; i <= M; i++) {
	a[p] = i;
	dfs(p+1, a);
	}
	}
	}
	void init() {
	fact[0] = 1;
	for (int i = 1; i < 16; i++)
	fact[i] = i * fact[i-1];
	dfs(0, new int[N]);
	debug("size = ", digits.size());
	}
	void solve() {
	R = sc.nextInt();
	N = sc.nextInt();
	M = sc.nextInt();
	K = sc.nextInt();
	init();
	long[] x = new long[K];
	for (int k = 0; k < R; k++) {
	if (k % 100 == 0)
	debug("R = ", k);
	for (int i = 0; i < K; i++)
	x[i] = sc.nextLong();
	long ret = -1;
	double best = -1;
	for (int i = 0; i < digits.size(); i++) {
	double prb = 1;
	Map<Long, Integer> product = products.get(i);
	for (int j = 0; j < K; j++) {
	if (!product.containsKey(x[j]))
	prb = 0;
	else
	prb *= product.get(x[j]);
	}
	prb *= ptrCnt.get(i);
	if (prb > best) {
	ret = digits.get(i);
	best = prb;
	}
	}
	System.out.println(ret);
	}
	}
	void run() {
	int caseN = sc.nextInt();
	for (int caseID = 1; caseID <= caseN; caseID++) {
	System.out.printf("Case #%d: \n", caseID);
	solve();
	System.out.flush();
	}
	}
	void debug(Object... os) {
	System.err.println(deepToString(os));
	}
	public static void main(String[] args) {
	new C().run();
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub