Google Code Jam 2011 反省

総括

A -> C -> B の順に解いていった. D はちゃんと読んでないけど, 読んですぐ解けるのを選んでいった.

問題読むのにも時間かかるのでこの方針は間違ってないはず.

Problem A

順調に解け問題無し. 細かい計算をもっと速く実装できるように鍛錬.

Problem C

英語の読み間違いにより時間をロス. 英語をすらすらと読めるようになろう.

素数がらみの問題だと分かったが, 素数生成で手間取る. こういうのは予めメモリサイズや速度を考慮したライブラリを自分で作っておくべき. 去年と同じく Big の方でメモリサイズを考えずにプログラムを走らせ, swap しまくりで遅くなり expired. 無念.

終わってから大きい方の素数について無駄な計算をしていることに気付く. 枝刈りの感覚重要.

Problem B

総当たりっぽかったのでいったん避けたが, やっぱり総当たりしか方法が無さそう. 最初から解けば良かった.

Python で解いていたが, debug に手間取り時間切れ.

追記

他の人のつぶやきを見ていて気付いたこと.

Problem B で総和を何度も求めているが, そこのコスト計算をしてなかった. 範囲を変えて総和を求める場合のチューニング方法を知っておくべき. 先頭からの和を取って事前処理をしておけば, 部分的な総和は O(1) で求まる.

Licenses