昨日、Google Code Jamの日本国内限定版であるGoogle Code Jam Japan http://code.google.com/codejam/japan に出場。時間ギリギリでCのsmallを解くことができ、結果は100位。何とか目標にしていたTシャツ圏内(200位)に滑り込めた。以下、簡単な記録。
A. アンテナ修復
当てずっぽうで、単純にアンテナを長い順にソートして提出→WA。反省して、全並び順を試して愚直に面積最大となる方法を探してsmall通過。
次に、smallの結果を眺めると、「最も長いアンテナの位置をCとすると、2番目に長いアンテナはC-1, 3番目に長いアンテナはC+1, 4番目に長いアンテナはC-2、5番目に長いアンテナはC+2、…」という法則がありそうに思えたので、その通り実装。結果、largeも通過。証明したわけでもないので、罪悪感がある。
B. バクテリアの増殖
粘ったが分からなかった。mod Cをとった値が1000回以内にループするというのは気付いたのだけど、うまく計算式に落とすことができなかった。
ちなみに、Wikipediaによると、観測可能宇宙内の原子数は約10^80個。この問題では、1000個のバクテリアは1時間後に1000^1000個 = 10^3000個に増殖することに。宇宙終了。（いつものことですが）
C. ワイルドカード
時間がなかったのでsmall狙いにした。まず、Aの文字列から正規表現の文字列をブルートフォースで作る。smallでは文字列の長さは最大10文字なのでありえる正規表現の数は2^10以下しかないので、ブルートフォースが可能。次に、AにマッチするがBにマッチしない正規表現を収集。マッチの判定はPerlの正規表現に任せた。そして、収集した正規表現の中から、問題分の条件に合う正規表現を1つ選んで出力しただけ。
D. クローゼットルームとE. 無限庭園
あまり合格者数が増えていないようだったので、怖くて放置。
感想
毎回、簡単に解ける問題と、力技で解ける問題しか解けていない。ちゃんとアルゴリズムを勉強しなければ次のステージには行けないというのがよく分かった。
