TopCoder SRM 418 DIV1
イエローコーダーとして初めてのSRM。さてこの地位を保てるか。
Coding Phase
- 250点問題
- 高校の数学Ⅰでありそうな組み合わせの問題。最大サイズが小さいので、どんな方法で解いても時間オーバーになる心配はまずない。トラップになるような箇所もなく、ただの早解き大会だった。こういうのはさっと早解きだということを見極めて、5分くらいで終わらせられるようにならなきゃだね。
- 500点問題
- まず単純に再帰で書いたら、最悪のケースでは実行時間オーバーになった。そこでキャッシュを効かせようとしたけど、うまくいかなくて時間切れ。チャレンジのときに他の人のコードを見ていて、どこが間違ってたのか分かった。もう一歩だったなー。【あとで確かめる】
こういうのって500点問題の一つのパターンなんだろか。- 単純な再帰での解法は時間オーバー
- 繰り返し構造が出てくるところでキャッシュする
- 実行時間と使用メモリ量の兼ね合いでキャッシュサイズを調整
これがDPというやつか。だんだん分かってきたぞ。
Challenge Phase
うおっ、自分以外の全員がC++だ！ 肩身が狭い。
500点問題をキャッシュさせずに解いてる人を発見したのでチャレンジしようとしたら、タッチの差で先に撃墜されてしまった…。
他にもキャッシュ無しで解いてるっぽい人がいたのでそちらにチャレンジしてみたら、あえなく失敗。コードをよく読んでみるとちゃんとキャッシュされていた。早とちりはだめだね。
まあ今回は初チャレンジができただけでもよしとしよう。あのテストケース作るUI、慣れないとけっこう操作しづらいので。
System-Testing Phase
全体的に落ちてる人少なめ。今回はチャレンジ〜システムテストがあまり盛り上がらない問題セットでした。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Passed System Test | 17:34 | 187.94 |
| 500 | Compiled | 57:03 | 0.0 |
| 900 | Unopened | - | 0.0 |
チャレンジ1回失敗 -25.0
スコア 162.94 / 616人中454位 / レーティング 1513→1454
黄色からは落ちてしまったけれど、成長していることが実感できたので悲観してはいません。250点問題を時間かかってもいいから確実に取ってれば大きく下がることはないし、たまに500点問題を解ければすぐ戻ってこれる。
