Google Code Jam 2013 Round 2

Code JamのRound 2がありました。

惜しくもGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れられるか入れられないかギリギリのラインで終わってしまいました。

去年もGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツラインにぎりぎり届かないくらいの順位でしたが、ルール違反とかで上の人が数十人ほどいなくなって、なんとかGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れることができました。

なので、今年もGoogleに認められた世界レベルのプログラマーだけが着用することを許されたTシャツを手に入れられる可能性はまだ残っているわけです。

本番終了後、二分探索の上限の初期値をnとすべきところを(n+1)としていたのが発覚して、もしそれがなかったらGoogleに認められた世界レベルのプログラマーだけが着用することができるTシャツを確実に手に入れられてたと思うと残念でなりません。
それどころかこのミスがなければ、Round 3行けてたみたいです。いやー、悔しい。

ただ今回のCode JamでRound 3行きがもはや手の届かないレベルじゃ無くなったというのが分かったので、来年はRound 3進出を目標にしようと思います。

復習のため、A, B, CをJavaで解いてみました。Dは解ける気がしないので放置。

Ticket Swapping

損失が最大になるように乗客を降ろす = 後で乗ってきた人を先に降ろす（降りるべき人が後で乗ってきた人のチケットを使って降りる）が成り立つことに気づけばstackを使って解けます。LIFOです。

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 Main {
	static final long MOD = 1000002013;
	Scanner sc = new Scanner(System.in);
	
	long cost(long x, long y, long n, long p) {
		long ret = (y - x) * (n + n - y + x + 1) / 2 % MOD;
		ret = ret * p % MOD;
		return ret;
	}
	
	void solve() {
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] s = new int[M];
		int[] t = new int[M];
		int[] p = new int[M];
		int[] q = new int[M];
		
		for (int i = 0; i < M; i++) {
			s[i] = sc.nextInt();
			t[i] = sc.nextInt();
			p[i] = sc.nextInt();
			q[i] = p[i];
		}
		
		Set<Integer> stations = new TreeSet<Integer>();
		for (int i = 0; i < M; i++) {
			stations.add(s[i]);
			stations.add(t[i]);
		}
		
		long ret = 0;
		// legal ride
		for (int i = 0; i < M; i++) {
			ret += cost(s[i], t[i], N, p[i]);
			ret %= MOD;
		}
		
		// illegal ride
		int[] stack = new int[2*M];
		int size = 0;
		
		for (int k : stations) {
			// get on the train
			for (int i = 0; i < M; i++) {
				if (s[i] == k)
					stack[size++] = i;
			}
			
			// get off the train
			long cnt = 0;
			for (int i = 0; i < M; i++) {
				if (t[i] == k)
					cnt += q[i];
			}
			
			while (cnt > 0) {
				int x = stack[--size];
				if (cnt >= p[x]) {
					ret -= cost(s[x], k, N, p[x]);
					ret = (ret % MOD + MOD) % MOD;
					cnt -= p[x];
					p[x] = 0;
				} else {
					ret -= cost(s[x], k, N, cnt);				
					ret = (ret % MOD + MOD) % MOD;
					stack[size++] = x;
					p[x] -= cnt;
					cnt = 0;
				}				
			}
		}
		
		System.out.println(ret);
	}

	void run() {
		int T = sc.nextInt();
		for (int id = 1; id <= T; id++) {
			System.out.printf("Case #%d: ", id);
			System.err.printf("Solving Case #%d...\n", id);
			solve();
			System.out.flush();
		}
	}

	void debug(Object... os) {
		System.err.println(deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Many Prizes

• 賞品が必ずもらえる。
• 賞品をもらえる可能性がある。

のどちらも再帰的に判定できます。また、関数がmonotonicなので二分探索が使えます。

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 Main {
	Scanner sc = new Scanner(System.in);

	boolean shouldWin(long n, long p, long x) {
		if (p <= 0) return false;
		if (n <= p) return true;
		if (x == 0) return true;
		return shouldWin(n/2, p-n/2, (x-1)/2);
	}
	
	boolean canWin(long n, long p, long x) {
		if (p <= 0) return false;
		if (n <= p) return true;
		if (x == 0) return true;
		if (x == n-1) return canWin(n/2, p-n/2, n/2-1);
		else return canWin(n/2, p, (x+1)/2);
	}
	
	void solve() {
		long N = sc.nextLong();
		long P = sc.nextLong();
		
		N = 1L<<N;
		
		long x = 0;
		long y = N-1;
		
		long lo = 0;
		long hi = N;
		
		while (hi - lo > 1) {
			long mid = (lo + hi) >> 1;
			if (shouldWin(N, P, mid))
				lo = mid;
			else
				hi = mid;
		}
		x = lo;
		
		lo = 0;
		hi = N;
		while (hi - lo > 1) {
			long mid = (lo + hi) >> 1;
			if (canWin(N, P, mid))
				lo = mid;
			else
				hi = mid;
		}
		y = lo;
		
		System.out.println(x + " " + y);
	}

	void run() {
		int T = sc.nextInt();
		for (int id = 1; id <= T; id++) {
			System.out.printf("Case #%d: ", id);
			System.err.printf("Solving Case #%d...\n", id);
			solve();
			System.out.flush();
		}
	}

	void debug(Object... os) {
		System.err.println(deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Erdős–Szekeres

問題の導入がおもしろいです。

「整数[1,N]のpermutationは最低でも長さsqrt(N)の部分増加列または部分現象列を持つ。」らしいです。

なぜそうなるか簡単に考えてみました。

まずすべてのi, j, i < jについて(A[i], B[i])と(A[j], B[j])は必ず異なることを示します。
X[i] < X[j]ならA[i] < A[j]です。
また、X[i] > X[j]ならB[i] > B[j]となります。よってすべてのi, j, i < jについて(A[i], B[i]) , (A[j], B[j])は異なります。

あとは鳩ノ巣原理を使えば、すべてのiについてA[i] < sqrt(N)かつB[i] < sqrt(N)であれば矛盾することがわかるので、A[i] >= sqrt(N)またB[i] >= sqrt(N)となるようなiが存在することが分かります。

話が脱線しましたが、問題自体は

1. A, Bのリストからトポロジカル順序を求める
2. ワーシャルフロイドで推移閉包を求める
3. トポロジカル順序に矛盾しないようにかつなるべく辞書順が最小になるように数字をあてはめていく

というふうな感じで解けます。wataさんのコードがわかりやすいです。