先日開催されたGCJ2010のオンライン予選に参加しました。
ここんところ就活漬けで、コンテスト系のコードにはあまり触れられてなかったんですが、
自分にしてはまずまずの出来だったと思います。

結果から先に言うと、
(small,large)
A (o,o) +33p
B (x,x)
C (o,x) +10p
43p
で、5809位でした。

A, Snapper Chain

問題文を解読するのに時間がかかった。
解読し終わった後に最終的に式に落とし込めそうな気がしたので、
ちょっとずつ共通項をあぶり出していった。

まず、Nに対する手数は固定で、max(N)=30だったので、先に計算して辞書でOK
加えて、電気が付いている状態というのは、コストとほぼ同義。
一度点いたあとはスナッパーが全部OFFになるので、その後は１を挟んで繰り返し。

	public SnapperChain(Scanner sc, PrintStream ps){
		int[] dic = new int[31];
		dic[1] = 1;
		dic[2] = 3;
		for (int i = 3; i <= 30; i++) {
			dic[i] = (dic[i - 1] - dic[i - 2]) * 2 + dic[i - 1];
		}

		int T = sc.nextInt();
		for (int i = 1; i <= T; i++) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			int cost = dic[N];

			while(true) {
				K -= cost;
				if (K <= 0) break;
				K--;
			}

			if (K == 0) {
				ps.println("Case #"+i+": "+"ON");
			} else {
				ps.println("Case #"+i+": "+"OFF");
			}
		}

		ps.close();
	}

B, Fair Warning

集中力がきれていて、もうさっぱりわからなかった。
ひとまず、BigInteger使ってひたすら枝刈りした方針は合っているんだろうか？
smallすら通らなかった。

解法は後で読みます。

http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=1

C, Theme Park

smallは問題文の通りコードに起こすだけなので、small正答率も一番高かった模様。
けど、largeはそう簡単には通らないよね。
つい面倒くさくなってすぐlargeやったら通りませんでした。反省してます。

これも後で解法読んで書き直します。

http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=2

	public ThemePark(Scanner sc, PrintStream ps) {
		int T = sc.nextInt();
		for (int i = 0; i < T; i++) {
			int R = sc.nextInt();
			int K = sc.nextInt();
			int N = sc.nextInt();

			int[] group = new int[N];
			for (int j = 0; j < N; j++) {
				group[j] = sc.nextInt();
			}

			long res = 0;
			int index = 0;
			int startIndex = 0;
			for (int j = 0; j < R; j++) {
				startIndex = index;
				int k = K;
				while (true) {
					if (k >= group[index]) k -= group[index++];
					else break;
					if (index == N) index = 0;
					if (startIndex == index) break;
				}
				res += K - k;
			}

			ps.println("Case #"+(i+1)+": "+res);
			System.out.println("Case #"+(i+1)+": "+res);
		}
		ps.close();
	}

Result

予選は通過できたのは良いこと。
だけど、6000位近いポジションじゃぁ次で落ちるなあ。

もっと頭柔らかくして、しっかり準備して次にのぞもうと思います。