Google Code Jam Japan 2011 決勝

A. 5 + 10 = 15
B. small落ちた
C. small落ちた

結果.
15点で276位。
つまりTシャツは落としました。

• A. アンテナ修復

長い棒が隣り合うようにすればよい。
蟻本のP107を参照してください。

テンプレート省略。

const double PI = M_PI;
double rad;
double area(int i, int j) {
	double ret = sin(rad) * i * j / 2.0;
	return ret;
}

int main() {
	int T; cin >> T;
	for(int round = 1; round <= T; round++) {
		int K; cin >> K;
		vector<int> E(K);
		rep(i,K) cin >> E[i];

		sort(E.begin(), E.end());
		rad = (360.0 / K) / 180 * PI;

		double sum = 0.0;
		sum += area(E[0], E[1]);
		sum += area(E[0], E[2]);
		int prev_a = E[1];
		for(int i = 3; i < K; i += 2) {
			sum += area(prev_a, E[i]);
			prev_a = E[i];
		}
		int prev_b = E[2];
		for(int i = 4; i < K; i += 2) {
			sum += area(prev_b, E[i]);
			prev_b = E[i];
		}
		sum += area(prev_a, prev_b);

		printf("Case #%d: %.7f\n", round, sum);
	}
	return 0;
}

• B. バクテリアの増殖

Rubyでsmallに逃げようとしたけれど、Rubyでは通らずにPythonとJavaでは通るらしい。／(^o^)＼ﾅﾝﾃｺｯﾀｲ

• C. ワイルドカード

正規表現でガリガリ実装したら、なぜか落ちた。あとでデバッグしよう。。。

#!/usr/bin/env ruby1.9.1
T = gets.chomp.to_i
1.upto(T) do |round|
  a = gets.chomp
  b = gets.chomp
  ans = []

  if b !~ /^#{a}$/
    ans << a
  end

  a.size.times do |n|
    tmp = a[n ... a.length]
    if b !~ /^.*#{tmp}$/ 
      ans << "*" + tmp
      tmp.length.times do |m|
        s = tmp[0..m]
        if s.size == 0
          next
        end

        if b !~ /^.*#{s}.*$/
          ans << "*" + s + "*"
        end
      end
    end
  end

  a.size.times do |n|
    tmp = a[0..n]
    if b !~ /^#{tmp}.*$/
      ans << tmp + "*"
      tmp.length.times do |m|
        s = tmp[m ... tmp.length]
        if s.size == 0
          next
        end

        if b !~ /^.*#{s}.*$/
          ans << "*" + s + "*"
        end
      end
    end
  end

  minlen = ans.map{|s| s.length}.min 
  ml = ans.select{|s| s.length == minlen}
  minasta = ml.map{|s| s.count("*")}.min
  ma = ml.select{|s| s.count("*") == minasta}

  puts "Case ##{round}: #{ma.min}"
end