2008年7月27日日曜日

Google Code Jam 2008 Round 1にて敗退

3つのサブラウンドに分かれて実施された、Google Code Jam 2008 Round 1 が開催されました。私は Round 1B および Round 1C でのエントリーとなりましたが、残念ながらここで敗退という結果になりました。

予選に比べて問題の難易度が上がり、Round 1A を観戦している段階で危機感を感じていたのですが、英語力やプログラムをすばやく書く訓練が足りなかったのが敗因だと思います。もちろんアルゴリズムそのものについての定跡研究が足りていないというのが一番なのかもしれません。仮に次回も参加するとして、どういったトレーニングを積めばいいのかというのがすぐには思いつかず、せいぜい過去問・練習問題を数多くこなすということやTopCoderなどの他のコンテストに参加するというくらいなのかもしれません。とはいってもTopCoderは使える言語やコンテストのシステム的にちょっと肌に合わないので参戦するのに躊躇しているところです。

今回の獲得ポイントとしては、Round 1B で 5点、 Round 1C で 15点と共に Problem A しか歯が立たなかったという状況で、 Round 1C についてはもう5分早く書ければギリギリ通過という結果でした。振り返ってみると、時間が2時間になる本選ではアルゴリズムとスピードと英語力が求められるという点で非常に過酷な戦いだったのかもしれません。評価点としては予選の問題をたくさん時間をかけてなんとか全部答えられたというところでしょうか。

コンテスト全般を通じて楽しめた要素はそれなりにあったのですが、プログラミングという「種目」そのものが本質的に自分と孤独に戦うという要素が多く結構なストレスを感じる一方、カタルシス的な要素が比較的少なく、それを理解できる人間も限られるということで、一般向けにアピールするにはなかなか難しい分野なのかもしれないというのが率直な感想でした。勝ち残った皆さんの健闘を祈ります。

追記:
Round 1 でペナルティタイムの計算方法が変更があり Small の時間のみが考慮されるルールに変更されましたが、スコアボードを見るとどうやら影響を受けていたようでSmallの問題を一刻でも早く回答するのがより重要な要素になっていたようでした。仮に今回ギリギリ通過しても、間違いなく次で落とされるでしょうし、くやしかったらもう1問解けということになるのですが、ここにきてルールが変更されるというのはいかがなものでしょうか。

確かに予選ラウンドではペナルティタイムは通過の要件とは関係がなかったのですが評価基準の一貫性を崩してしまったことについては関係者の熟考を求めたいところです。また、Round 1C の Problem A ではコンテスト中に問題文が修正される事態が生じたり、こちらで議論されているところを見ると、ローカルサイト出場者が18歳以上であることを確認する手段を現段階で用意していなかったりと、結構杜撰な部分が出てきているようにも見受けられます。前回とは違うシステムを使っての初めてのコンテストだということもあるのでしょうけれども、しっかり運営してほしいところです。

2008年7月25日金曜日

Google Code Jam 2008 QR Problem A

先日予選が行われたGoogle Code Jam 2008 予選ですが、無事ラウンド1 へ進出できたようです。

ラウンド1 は3つのサブラウンドに別れ、参加者は3つのサブラウンドのうち2つまでに参加し、それぞれのラウンドで上位840人、合計で2520人が次のステージに進むことができます。このラウンドからコンテストの時間が2時間になるのでなんとか勝ち抜けるように頑張りたいと思います。

さて、そんなこんなで突破した予選や練習問題・ベータ問題について、復習も兼ねて解説を試みたいと思います。今日は予選のA問題 "Saving the Universe" です。

予選で提出したコードは下の通りです。
#! /opt/local/bin/python
# -*- coding: utf8 -*-

def do_calc(num_engine, query):
change = 0
flags = [0] * num_engine

for q in query:
flags[q] = 1
if flags.count(0) == 0:
flags = [0] * num_engine
flags[q] = 1
change += 1

return change


def main():
for c in range(input()):
dic_engine = {}
query = []
num_engine = input()

for i in range(num_engine):
tmp_str= raw_input()
dic_engine[tmp_str] = i

num_query = input()

for i in range(num_query):
str_query = raw_input()
query.append(dic_engine[str_query])

change = do_calc(num_engine,query)

print 'Case #%d: %d' % ( c+1, change )

if __name__ == '__main__':
main()

予選が終わって IRC #gcj や google-codejam ではDPだDPなんて話になっていましたが、検索エンジンごとにフラグを作り、全てのフラグが立った瞬間が検索エンジンの切り替え時とみなして数えあげるというアルゴリズムです。フラグ立ては美少女ゲーマーの人が得意ですね(謎)

予選では、検索エンジンを切り替えた時の flags[q] = 1 の部分を忘れてSmall Input を処理して、1 wrong try を出してしまいました。また、パースするときについでに検索エンジンやクエリーを数字に置き換えていったのですが、この程度のものではそこまでしなくても問題が出なかったかもしれません。数字に置き換えたことで見通しのよいコードになったので、それなりの意義はあったと思います。

人数的には正解者が一番多いのがこの問題だったわけですが、このようなコードを24時間内に提出し、Small / Large の両データセットを処理すればいいわけですから、予選を通過することそのものはそんなに難しくはなかったのかもしれません。

2008年7月18日金曜日

Google Code Jam 2008 参戦

Google のプログラミングコンテスト Google Code Jam 2008 の予選(Qualification Round)が日本時間で17日の午前8:00から開催されました( Google Japan Blogでの紹介記事 )。

個人的に最近はあまりプログラムを書かなくなってきたのですが、ここ最近いじっていた DjangoGoogle Application Engine で使われている Python の理解を深めることと、練習問題にハマってしまったので、本格的に参戦ということになりました。使用言語はもちろん Python です。

基本的な流れとしては、出題された問題を解決するプログラムを参加者が作成し、用意されたデータを作成したプログラムに入力して処理を行い、出力とソースコードをアップロードし、出力が正しければポイントがもらえるという仕組みです。

予選に向けて練習問題を解いてみたら自分にとって難しい問題も出題されるようなので、予選当日は仕事を休み時間を最大限確保して望んだところ、すべての問題・データセットでポイントを得て予選ラウンドで177位という成績となりました。問題がなければ次のラウンドに進めそうです。

ただ、やはりまだまだ問題を解くスピードが遅いという課題があるのも痛感いたしました。英語の問題文を迅速に読み題意を理解することが次のラウンドまでの課題でしょうか。上位陣は小一時間程度でノーミスで解いているわけで、少しでも近づけるように努力せねばなりません。