Google Code Jamに参加中
http://code.google.com/codejam/
参戦記です。
僕のスペック
SIerで組み込み系の受託開発をしている31歳既婚。猫犬あり。
形態素解析器の開発をしていたことがあるためか、DP大好き。A*アルゴリズムが好きです。でもAアルゴリズムはもっと好きです。
TopCoderには1回だけ参加し、Ratingは1197(緑色。1200から青)。
第一言語はJava。
Qualification Round
75点中30点で通過。通過ラインは25点。
A. Saving the Universe
簡単に考えればいいものをDPで解いてしまう。正解。
B. Train Timetable
ルールを勘違いして、Long問題をタイムアウトさせてしまう。失敗。
C. Fly Swatter
A問題は流石に出来ただろうと思ったので、趣味でモンテカルロ法を使って面積を求めてしまう。計算時間が足りず提出できず(当たり前だ)。
Round 1A
100点中0点で予選落ち。通過ラインは2394人中の840位(15点、提出時間10:31)。情けない。
A. Minimum Scalar Product
問題を勘違いしていた。「数列の数字を2回だけ入れ替えて」解を最大にするのかと勘違いしていたが、数列の順番は任意だった。そんな、すぐ解けるがな……。とはいえ、英語を読む時間とプログラム書く時間(Javaを使用)を考えると、勘違いしていなくても10:31では解けてなかったと思うな。
B. Milkshakes
これも問題を勘違いしていた。顧客1人につきMaltedは最大でも1つ、という条件を見逃して解いていた。これ、まともな時間で解けるんかなあとは感じてた。
C. Numbers
見てなかった。
反省
問題文を勘違いするとどうしようもない。
自分のレベルを考えると、「確実に合格点を狙う」戦術をとるべきだった(最高点を狙うようなやり方はダメ)。計15点を取れば提出時間次第、20点を取れば確実、ということがわかったので、20点狙いで行くことにする。
実はC問題がねらい目。A問題に比べポイントが3倍も付くが、難しさは3倍も変わらない。A問題は素早く問題文を理解しないと、低ペナルティ時間で解くのが難しい気がする。
Small問題は総当たりで解けるので、A問題とC問題のSmallを総当たりで解こうと決意。
Round 1B
100点中20点で通過。通過ラインは15点、1:39:09。
A. Crop Triangles
問題文の意味がよくわからなかったので、しばらく読み返す。こういう、問題の本質以外の文書が多い問題は苦手だ。
予定通り、Smallを総当たりで解いて提出。
B. Number Sets
これも変に勘違いして解けなかった……。
C. Mousetrap
予定通り、Smallを総当たりで解いて提出。マルチコアCPUでマルチスレッド使って解いて約3分かかってしまったので、危なかった。
反省
Smallを総当たりで解く作戦でなんとか通過したものの、なんか空しい。
問題文を読むのに時間がかかりすぎるとか、勘違いするとか、これはなんとかしたいがなんとかならないだろうな。
あと、コンペティション用の書き方を練習すべし。new ArrayList
C++のSTLにはないデータ構造を使い出した時点で、何か危ないんじゃないかと考え直さないとダメだ。TreeSetのNavigableSetインタフェースとか要注意。
落ち着いて時間書ければLargeも解けるので、落ち着いて解きたいところ。
JavaじゃなくてC++で書いたほうがいいのかなあ。Javaの回りくどい書き方はコンペティション向きじゃない。
Round 1C
観客として参加。問題が解ける解ける。これが傍目八目というやつか。
A. Text Messaging Outrage
あっさりLargeが解ける。
B. Ugly Numbers
Smallは難しくない(けどマルチスレッド使って3分強かかる解き方をした)。
Largeが難しい。1時間くらい考えて、先頭の文字から順にDPで解いていけばいいことに気づく。210の剰余系なのか。C問題の方が簡単だと思うんだけど……。
C. Increasing Speed Limits
SmallとLargeが同程度の難易度(だと思う。Smallも探索範囲が広いから総当たりできないような気がする)。後ろから解決していくタイプのDP。
