Google Code Jam Japan 2011 で撃沈したよ

Google Code Jam

A. 5 + 0
B. 0 + 0
C. 5 + 13

結果. 23点で413位

人権が危うい。
精進しなければ...

※ソースコードは「続きを読む」から。TeX記法を乱用しているので、見られなかったらごめんなさい＞＜
A -> C -> Bの順に解きましたが、私用があったため、Bのsmallを解いている間に時間切れとなりました。

A. カードシャッフル

1 \leq M \leq 10^9だったら配列確保できないなぁ。
1. 範囲だけを保存
2. 逆順に再帰的に
のどっちかなんじゃないかなぁ。

でも1の方法はカットの回数が多くなったら結局メモリ足りなくなりそうだなぁ。
2の方法はどうやって書けばいいんだろう...

  • > ナイーブな方法でsmallだけ提出。

B. 最高のコーヒー

DPっぽいなぁ。
1 \leq K \leq 2\times10^{12}ってことはO(KN)駄目じゃん・・・

  • > 私用から帰宅後、O(NlogN + KN)な貪欲でsmallは通った。

C. ビット数

N \leq 10^{18}って事はO(logN)くらいのオーダーか数学的解法のどっちかだろうなぁ。

ちょっと見てみましょう。
以下かなり見にくいシミュレーション結果。

N a b max
1 1 0 1
2 1 1 2
3 3 0 2
4 3 1 3
5 3 2 3
6 3 3 4
7 7 0 3
8 7 1 4
9 7 2 4
10 7 3 5
11 7 4 4
12 7 5 5
13 7 6 5
14 7 7 6
15 15 0 4
16 15 1 5
17 15 2 5
18 15 3 6
19 15 4 5
20 15 5 6
21 15 6 6
22 15 7 7
23 15 8 5
24 15 9 6
25 15 10 6
26 15 11 7
27 15 12 6
28 15 13 7
29 15 14 7
30 15 15 8
31 31 0 5
32 31 1 6

はい、明らかに法則性ありますね。

2^p-1 \leq N（pは非負の整数）となる最大の値を求めればいいみたいです。
log使ってO(1)出来るかも。


ソースコード集

A.

smallだけ通ったコード。

import java.util.Scanner

object Main {
	val sc = new Scanner(System.in)
	
	def main(args: Array[String]) {
		for (T <- 1 to sc.nextInt) {
			val M = sc.nextInt
			val C = sc.nextInt
			val W = sc.nextInt
			var cards = List.range(1, M + 1)
			for (c <- 0 until C) {
				val a = sc.nextInt
				val b = sc.nextInt
				val middle = cards.slice(0, a - 1)
				val front = cards.slice(a - 1, a + b - 1)
				val end = cards.slice(a + b - 1, cards.size)
				cards = front ++ middle ++ end
			}

			val ans = cards(W - 1)
			printf("Case #%d: %d\n", T, ans)
		}
	}
}

B.

同じくsmallだけ。

int main() {
	int T; cin >> T;
	for(int round = 1; round <= T; round++) {
		int N; cin >> N;
		ll K; cin >> K;
		vector<pair<int, pair<ll, ll> > > data(N);
		rep(i,N) cin >> data[i].second.first >> data[i].second.second >> data[i].first;
		sort(data.rbegin(), data.rend());
		vector<int> arr(K);
		rep(i,N) {
			ll t = data[i].second.second;
			ll c = data[i].second.first;
			int s = data[i].first;
			for(int day = t; day >= 1 && c > 0; day--) {
				if(arr[day - 1] < s) {
					arr[day - 1] = s;
					c--;
				}
			}
		}
#if 0
		puts("before");
		rep(i,K) {
			printf(" %d", arr[i]);
		}
		puts("");
		puts("after");
#endif

		int ans = accumulate(all(arr), 0);
		printf("Case #%d: %d\n", round, ans);
	}
	return 0;
}

C.

オーバーフローが怖かったのでRubyで。

#!/usr/bin/env ruby1.9.1

t = gets.chomp.to_i
1.upto(t) do |round|
  n = gets.chomp.to_i
  cnt = 0
  0.upto(64) do |i|
    if (1 << i) - 1 > n then
      cnt = i - 1
      break
    end
  end
  a = (1 << cnt) - 1
  b = n - a
  ans = sprintf("%b", a).count("1") + sprintf("%b", b).count("1")
  puts "Case ##{round}: #{ans}"
end