SRM260 - TopCoder への挑戦のはじまり

Hayato Ito

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

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

Chat Area

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

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

ということです．この 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 するまでの時間が早ければ早いほどポイントが高くなります．

SUBMIT_RESULT__

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

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

CHALLENGE__

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 )

Room Statistics

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

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

Rating

今日の教訓

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