TopCoder はじめました

半年前くらいからずっとやりたいなぁと思っていた TopCoder に先週 SRM 425 で初挑戦しました。

言語は C#, C++, Java のどれもまともに書いたことなかったので、どうせ覚えるならと言うことで C++ を選択。C++ の知識は「vector は聞いたことあるけど、それに要素を追加するときのメソッドはリファレンスを見ないとわからない」くらいのレベル。C の理解度も、入門書のポインタが出てきたあたりくらいまでです。
ちなみにコンピュータサイエンスとかのそういうバックグラウンドは一切持ち合わせておりません。高校くらいまでの数学は好きでした。

結果はこんな感じでした。初参加ですので DIV2 です。

250点問題

最初よくわからず何回か test に失敗した後 min * max で submit

Point	215.75	Coding Time	11:42

500点問題

普通に思いついたとおり再帰で実装。しかし実行してみると90秒ほどかかった。
どうして良いかわからずあたふたしてたらタイムアップ。

1000点問題

Unopened

Challenge phase

250点問題で factors.size() == 1 の時に2倍するだけというのがいくつかあったので、片っ端から {3} を入力。4人成功。
500点問題で自分と同じようなアルゴリズムの人を探して、これタイムアウトだろと思い挑戦するも1人失敗。

Point	175.00

結果

Point	390.75
Room Place	1 / 20
Division Place	97 / 921
Rating	1200 -> 1403

メンバーに恵まれ Challenge がうまくいったおかげで部屋1位でいきなり DIV1 に上がれてしまった。DIV2 の Medium, Hard が DIV1 の Easy, Medium らしいので*1、今回の感触で行くと次回1問も解けないことがほぼ確定した。

500点問題は他の人の感想を見る限り、普通に再帰で深さ優先探索で間違ってなさそう。でも「全探索してもこれくらいのオーダーだから問題ない」とかそういう感覚が全くわからない。やってるうちに身についていくものなのか一度基礎からちゃんとやらないとダメなのか。
まあそれ以前にタイムアウトしてしまうコードができるとこまでで40分くらいかかってるのでその方が問題かも。DIV1 の人はだいたい10-20分くらいで解いてるっぽい。アルゴリズムを考える方を鍛えるのは簡単にはいかないだろうけど、コンテスト中は STL のリファレンス引かないでも書けるくらいにはならないとダメだなぁ。

次回 DIV2 になると思われるので、次々回以降は DIV1 入りを目標にします。

*1:いつもそうかは知りません