TopCoder とは，世界中のトッププログラマが集まり，プログラミングスキルを競いあっているサイトです．毎週のようにオンラインでプログラミングコンテストが行われています．面白そうなので参加してみました． SRM260 に挑戦です．SRM とは Single Round Match のことです．定期的に（週に 1 回ほど）開催されています．

先日開催された Google Code Jam 2005 でこのサイトを知った人が多いのかいつもより参加者が多いらしく（私もその一人），驚いている様子が伺えます(800 名オーバー)．

レーティングが 1200 以上の人は Division1，それ以下の人は Division2 になります． Division1 の方が問題が比較的易しくなっています．初参加の自分は，Devision2．

簡単に SRM の流れをおさらいしておくと

• 開始時間の 5 分前までに Registration を行う
• 参加者は約 20 名づつ，Room にアサインされる
• 問題は 3 問．制限時間は 75 分．言語は Java, C++, C#, VB から選択できます．
• 5 分休憩
• 15 分のチャレンジタイム．この時間では，同じルームの参加者が提出したコードを見ることができます．バグを発見し「チャレンジ」に成功すると 50 ポイントもらえます．

ということです．この 4 つから選ぶなら(無難に?)Java でいきます．以下のような問題が出題されました．(code) は私が提出したコードです．

IsingModel (code)

250 点問題．特に難しいところはないです．軽くこなしたいところ．

GridPointsOnCircle (code)

500 点問題．中心(0,0)，半径 r の円上に座標が(整数, 整数)の形式を満たす点はいくつ存在する？って問題です． ちょっと，なやむ．単に (x, y) ( 0 <= x, y <= r) を全部調べていたらタイムオーバするってのが目に見えてるので，なんらかのちょっとした工夫が必要．

RollingBlock (code)

1000 点問題. サイズが rows x cols の盤上を 1 x 1 x 3 のブロックがごろんごろんと動くとき，ある地点からゴールの地点まで最短，何 Move で到達できるか？という問題です．条件として，

rows and cols will be between 1 and 100, inclusive.

とあるので，状態空間はたかだか 100 x 100 x 3 くらいです． BFS (Breadth First Search) で問題ない（はず）．不正な状態（盤からはみだす)をちゃんとチェックしてやれば，なんとかなるか．．

結果

制限時間つきでコーディングするなんていう経験が普段ないもんだから，あせるあせる．で，なんとか 3 問とも Submit しました．問題を Open してから，Submit するまでの時間が早ければ早いほどポイントが高くなります．

__

75 分のコーディングタイムが終了すると，5 分の休憩があります．その後，15 分間の Challenge Time が始まりました．

自分の 500 点コードが撃墜された瞬間．．

__

Challenge で使用されたパラメータ(円の半径)は入力条件の最大値である 2000000000 です．その結果は

"The code execution time exceeded the 2 second time limit."

2 秒以上実行時間がかかるのは認められないってことですね．．なるほど．．このように，あらかじめ，必要な上限のみに制限しておけば 2 秒以内だったか．．

long r = (long) Math.sqrt(rSquare) + 1;
long y = r;
for (long x = 0; x < r; x++) {

自分もどきどきしながらひとつ Challenge してみました．結果は成功(+50 点)．

Challenge Time が終わると，ひとまず終了です．全員の Submit されたコードに対して System Test が走ります． System Test に落ちると，どんなに早くその問題を Submit していてもゼロ点です．

System Test の結果です． ( Room Statistics )

250 点問題と 1000 点問題は無事 System Test に通りました． 1000 点問題は 2 回チャレンジをうけています．そんなに「間違えてる」ふうに見えたのかなー．

レーティングはこうなりました．

今日の教訓

• 2 秒以内という時間制限を忘れないように
• いちばん時間がかかるケースをちゃんと考慮しておくように

なかなか普段は味わえない緊張感があって，面白かったです. レーティングシステムというのがいいですね．また挑戦してみたいです．