Google Code Jam

http://d.hatena.ne.jp/yaneurao/20040909
http://www.topcoder.com/pl/?&module=Static&d1=google04&d2=login
ここで登録すると
http://www.topcoder.com/pl/?&module=Static&d1=google04&d2=arena
ここでもう今から本番で使われるJavaアプリケーションを立ち上げて練習用の問題を解くことができるようで、やってみた。問題は文章で指示された処理を入力に施して結果をreturnして出力してやる一個の関数を書かされるような形式。専用アプリケーション内でソースコードの編集からコンパイルからテストまででき、そのまま提出できる。問題のウィンドウを開いてからソースコード提出までに経過した時間に応じて点数がつくようになっているようだけど、提出されたものは後で自動でテストされて正しいものかどうか判定され、バグの存在が判明すれば点数が取り消されることになるらしい。

言語はC#、C++、VB、Javaの4つの内から好きなものが選べる。僕はここ最近C++しか触ってないのでC++を選んでみたのだけども、いきなり文字列の処理をやらされたりして、そうでなくともGCついてる言語よりも気を使わないといけない点が多いし、ちょっとC++不利か。stringだろうと躊躇しないでchar配列に落としたりsscanfを使っていくのが良さそう。あとで見て分かりやすいか、とか美観的な満足とかバカみたいなことは考えないで、とにかく完成スピード重視でいかないといけない。

本番前の練習として挑戦できる問題は3つ。

ベストな携帯のアンテナを探せ！

文字列からのトークン取得、配列内の検索、距離計算をさせられる。簡単。

抵抗値を算出せよ！

抵抗の配置構成情報が記述されている文字列の配列を処理して、全体の抵抗値を算出する。ちょっとした言語処理。再帰かスタックを使わせられる。簡単。

最短距離を算出せよ！

完全グラフのノード間最短距離を出すのだけれども、このグラフがちょっと普通ではなくて、ノードからノードに移動すると移動に要した時間に応じてグラフ全体の重みにランダムな微変動があるというもの。抽象的な問題になったと思ったらいきなりコレか！全件探索では解けない。なんらかの最短経路探索のアルゴリズムを使うのだけれど、教科書にのってるのを丸写しできるようなケースじゃない。激ムズでした。

最後の問題は難しいだけにそれだけ面白いです。他人が提出したソースコードを見ることもできるようになっているのだけれど、滅茶苦茶スマートな思考法で解いているのもあったりして、それを見て驚くのもまた面白い。いや、面白がっている場合じゃないんだよなぁ。本番が思いやられる。