TopCoder SRM 425 DIV1
寒くて指が動かしにくい季節です。最近お仕事であまりコード書いてないのでタイピングの調子がいまひとつ。
Coding Phase
- 250点問題
- 碁盤目上をロボットがランダムウォークする。4方向それぞれへ向かう確率はパラメータで与えられる（等確率というわけではない）。与えられたステップ数のあいだ、一度通ったマスを通らない確率を求めよ、という問題。
最大ステップ数が14なので再帰で。一度通った場所に来たらその場で枝刈りするから計算量は高々3^14くらいか。いつもより難しめの250点問題でした。けどずいぶん安定して素早く書けるようになってきた。 - 500点問題
- 5×5の碁盤目の枠内に何カ所かコマが置いてある（最大5カ所）。コマを1マスずつ動かして全部のコマをくっつけようとしたとき、最短で何手必要か、という問題。
状態空間が高々25C5=5万くらい なので、幅優先探索で。でもなんか時間かかりすぎてる…。最悪ケースで20秒くらい。というわけで提出断念。今回は取っつきやすい問題だと思ったんだけどなー。実際解けてる人かなり多い。
Challenge Phase
500点問題に付いてたサンプル入力が、一方向に全部のコマを集める戦略で上手くいくものしかなかった。なので、真ん中に集めないといけないパターンができてない人がいるかも、というあたりを狙って他の人のコードを見る。
が、複雑なコードばかりで読めない…。今回もチャレンジできず。
System-Testing Phase
250点問題は確保。
1000点問題のテストに間違いがあったらしく、再テスト実行中。待ちきれないので寝ます。
→初め1000点問題は全員が落ちてたのだけど、再テストの結果2人が正解になってました。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Passed System Test | 12:19 | 212.83 |
| 500 | Compiled | 61:15 | 0.0 |
| 1000 | Unopened | - | 0.0 |
チャレンジなし
スコア 212.83 / 666人中333位 / レーティング 1501→1528 なんか面白い順位だ。
今回も、500点問題の壁は突破できずか。いい加減500点が解けないとこれ以上は上がらないでしょう。
