読者です 読者をやめる 読者になる 読者になる

Google Code Jam Japan 決勝の記録


このエントリーをはてなブックマークに追加

昨日、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. 無限庭園

あまり合格者数が増えていないようだったので、怖くて放置。

感想

毎回、簡単に解ける問題と、力技で解ける問題しか解けていない。ちゃんとアルゴリズムを勉強しなければ次のステージには行けないというのがよく分かった。