Google Code Jam 2008 Qualification Round 雑感
というわけで、今年復活したGoogle Code Jam に興味本位で参加してみています。もともとアルゴリズムとかとてもとても弱いので、刺激を受けるためにも。QRは無事通過しました。
以下、状況
Saving the Universe
検索エンジン切り替えの最小回数を求める問題。アプローチは山のようにありそうだったのですが、すぐに思いついたのが、入力文字列を上から見ていったときに、検索エンジンそれぞれの出現する位置がもっとも遠いものを発見して(全部のエンジンが登場しなくなったらそこで終わり)、そこを始点にして再検索する、という流れでした。rubyで解きましたが、Array#slice とかでとても簡単に解けました。誰かが「DP使えれば余裕」というエントリを書いていたのですが、DPってなんだろう。
Train Timetable
指定された時刻表を満たす最小の列車の本数を求める問題。これは- 与えられたリストを時刻でソートする
- リストの一番最初のエントリを一台の車両に割り当てて、計算開始
- 往復できる限り時刻表リストをトレースしていきつつ、時刻表リストからはそのエントリをremoveする
- その電車がもう往復できなくなったら一台についての処理は終わり。
- 時刻表がemptyになるまで、上記「一番最初のエントリを一台の車両に割り当て」に戻って繰り返す
これもrubyで delete_at とかでやったような気がします。こちらも簡単でした。
Fly Swatter
各種パラメータの与えられたテニスラケットでハエをたたける確率を求める問題。いまだに解けていません。orz近似値は簡単に求められるのですが、xx.xxxx%オーダーの精度がマストなのでダメ。「絶対面倒だから手をつけるまい」と思っていた積分して場合わけしながら計算、というのが実はメジャーな方法だった様子。
精度の要件が6ケタでなければモンテカルロ法でも求められるとは思うのですが、このケースでは多分トラップですね。Largeセット8分はクラスタリングして分散処理するとかしないと間に合わないんじゃないかと思いました。
積分のほうは 四分円の領域を y<=(r^2-x^2) と決めて、積分したものから弦か空白領域の面積を求めていくアプローチだと思うのですが、そもそも積分が出来ていなくて涙目。教科書を掘り出したりしています。
