Google Code Jam Round1

ちゃんと起きたよ！でもめちゃくちゃ眠い。。。

• • • • -

終わった。
問題Aは解けたけども、問題Bを眺めて面倒そうだったので問題Cをして、勘違いで全然解けてなくて結局Aだけしか解けなかったorz

Aの解答。例のごとくファイルを開いたり閉じたりは省略している。二つの整数の列vec1, vec2が与えられるので、適当に並び替えて内積(vec1[0] * vec2[0] + vec1[1] * vec2[1] + ...)が最も小さくなるようにしなさい、という問題。片方が大きい値のときにもう片方も大きい値だと掛けた結果がすごく大きくなるので、片方が大きい値のときにはなるべく小さい値を持ってきたい。というわけで片方を昇順、もう片方を降順でソートして計算。(追記：reduce(add, ...)を使っているのは古い癖なのでsumを使うべきだね)

    num_test = int(fi.readline())
    for test_id in range(num_test):
        fi.readline() # num of elements. no needs
        vec1 = map(int, fi.readline().split())
        vec2 = map(int, fi.readline().split())
        vec1.sort()
        vec2.sort(reverse=True)
        from operator import add, mul
        result = reduce(add, map(mul, vec1, vec2))
        p("Case #%d: %d" % (test_id + 1, result))

他は時間内に終わらず。あれかー、SmallをLargeに挑戦するためのテストケースととらえていて、Largeを説けるようなアルゴリズムを考えようとしているのが行けないのか。とりあえずLargeが解けなくてもSmallは解けるようなアルゴリズムでSmallの得点を確実に拾いにいくべきだったのか。

そしてRank: 849だって！840人まで次に進めるんだよね。微妙に足りない。

• • • • -

Cでトップのスコアだった人のコードを見ると、なんか行列の計算になっている。なんだこの謎の行列は。

int main()
{
	matrix trans;
	trans.data[0][0] = 0;
	trans.data[0][1] = 1;
	trans.data[1][0] = -4;
	trans.data[1][1] = 6;

	int numCase, i, n;
	scanf("%d", &numCase);
	for (i = 0; i < numCase; i++)
	{
		scanf("%d", &n);
		n--;
		matrix tP = power(trans, n);
		int res = (tP.data[0][0] * 6 + tP.data[0][1] * 28+ 1000000) % mod;
		if (res == 0) res = 999;
		else res--;
		printf("Case #%d: %03d\n", i+1, res);
	}
	return 0;
}

• • • • -

うわーん！C SmallはC Smallだけ落とせればいいやスタンスで攻撃すれば落とせたじゃないか！たったこんだけのコードでpassするじゃんか！

    from decimal import Decimal
    num_test = int(fi.readline())
    VALUE = 3 + Decimal(5).sqrt()
    for test_id in range(num_test):
        n = int(fi.readline())
        result = int((VALUE ** n) % 1000)
        p("Case #%d: %03d" % (test_id + 1, result))

SmallとLargeは別物だなぁ。やっぱり。

• • • • -

C Largeの解説 by t33f
http://t33f.tumblr.com/post/43587848/gcj-2008-round1a-problem-c