■ [SRM]SRM495 
2011-01-27 25:00-（JST）
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14424&rm=307047
自分が参加するのは久々のrng回
| Level | タイトル | 試合中 | あとで | ひとこと |
|---|---|---|---|---|
| 275 | ColorfulCards | AC 10min | - | 思いつけて良かった |
| 500 | CarrotBoxes | Compiled | - | グラフは苦手意識 |
| 975 | StrangeElevator | Opened | - | 500よりも望みあったかもしれない |
- Coding
- 275
- 500
- グラフか…
- 各ノードから辿っていって開けるのはどれかを記録して、親ノードがあればそれにマージしていって枝が何個できるかという感じ？
- テキトーに作ってみると全然違ったので真面目に考える
- ちゃんと考えると、これは強連結成分をひとまとめにする、ということなのだと理解する
- そしてトポロジカルソートしてやるとなんかうまくできそう
- しかし強連結成分分解を書いたことがなかった！
- 蟻本を開いて即席で書く。蟻本さまさまである
- トポロジカルソートの先頭から未開封の箱が残り1つになるまで順に開いていくとき、何個開かないといけないか数える
- しかしサンプルが合わない
- トポロジカルソート作るときの順番によって必要な開封個数が変わることがある
- つまり「残り1つになったとき」という終了条件をうまく扱えていない。確かにサンプルのそのケースでは間違う
- 終了3分前に「最後にどれを残すか全通り試せばよい？」と思いついたがもう間に合いません
- やっぱり正しくないコードを書き始めてしまうのは完全に負けルートだなあ
- 500で早解き競争になることはないのだから、見切り発車で書き始めるのではなくノートにメモったりしつつじっくり考えるべし。今回は全部脳内でやっちゃってた
- 975
- 一応開いただけ。問題の理解もしてない
- Challenge
- 275はいろいろなコードがあるがサンプルが強そうなので何もできない
- 500をgreedyでやっている人を発見。しかし自分がeasyしか解けてないのと本当に落ちるかちゃんと検証する時間がなかったのとでチャレンジせず
- もし成功していてもあまり順位変わらなかったので結果的に自重して正解
- ほとんどの場合で「迷ったらチャレンジはするな」が良い戦略だと思います
- 例外は、自分が1問は確実に正解している自信があって、かつ順位表で自分の下がまばら・上が僅差 というとき
- あと、トーナメントで「これを撃墜しないと次のラウンドに進めない」という場合もある
- System Test
- 通った
結果
- スコア：245.73 + 0.00 + 0.00 + (50*0-25*0) = 245.73
- 順位：73位/697人
- レート：2322 -> 2334
highestへじわり接近
