GCJ予選通過

Google Code Jam 、Qualification Round の予選通過メールが届いた。次のラウンドは一週間後か。
今回の通過者は6773人のようです。次回は2520人が通過できるので、倍率2.7倍という計算。次ぐらいは何とか通過したいものです。

というわけで、Qualification Roundの感想を。

実行時間がシビアなものは無かったね。書いたプログラムを実行するのは各自の環境なので、マシン性能による差が出ないように考慮してるんだろうか。今後のラウンドもこうなのかな。

こういうプログラミングコンテスト系の催しはProject Eulerしか参加したことないので、アルゴリズムを考えたことがある対象が整数問題にちょっと偏ってます。今回の問題Cのように精度が意味を持つ数値計算が出てくると、とまどってしまう。TopCoderにはまだ手を出してないけれど、本気でやるなら参加して腕を磨いておいた方がよさそう。
しかし上位者のコード短いなあ。エレガントとはこういうことか！　という感じ。全員の提出した解答がダウンロードできるので、覗いてみると勉強になります。上位者はC++を使ってる比率が多いから読めないこと多いけど（C++わからない人です）。
ファイル入出力処理を書いたのって、初めてJavaを勉強したとき以来かも。もはや懐かしい…。

以下は問題ごとに。

A.Saving the Universe

頭から順番にクエリ文字列を検索エンジン名と比較して、全種類のエンジン名が出現したらカウントを一つ増やし、エンジン名の出現テーブルをリセットして続けるというだけ。ちょっと拍子抜け。
ほかの参加者の感想を見てたら、動的計画法がどうのこうのといった話がよく出てきてるけど…動的計画法ってなに？　→ググった。部分問題に分割して解いた結果をキャッシュして使うってことか？　それがこの問題とどう関係するのかはピンとこないけど。

B.Train Timetable

「電車の出発時刻がきた」・「電車が到着して出発準備完了になった」の2種類があるイベントオブジェクトを作って、時間でソートして順番に見ていくことで各駅でいくつの電車が必要かが分かる。
はじめ、同時刻に両方の種類のイベントが起こるケースの考慮ができてなかったので、一度不正解を食らってしまった。

C.Fly Swatter

モンテカルロ法でやろうかと一瞬頭をよぎったけれど、計算時間が馬鹿でかくなりそうだったのでやめて、空白の領域の面積を足していくというアプローチで。
積分せねばならんのかなあと思いつつ、図をぐりぐり書いてしばらく考えたら数値計算をやらずとも正確に求める方法が見つかりました。正方形と外周が交差しているケースは、扇形から三角形を足したり引いたりして。
純粋にアルゴリズムを考えるところ以外にも、コンパイルエラーと単純ミスに何度も悩まされ、なんだか自分の書いたものの抜けの多さが嫌になってくる。やっぱりテキストエディタ+javacの環境は辛いな。次からはEclipse使うか。
これはなかなか難しかった。2時間くらいかかった。このくらいが限界だー。