TopCoder SRM 422 DIV1
今回からハチロク世代TopCoder部でチャットしながらのSRM。これは楽しいし勉強になる。
Coding Phase
- 250点問題
- 組み合わせで確率を計算して足し合わせるだけ。今回はほとんどミスなくスムーズにいけたぞ。少し練習した成果が出てきてます。
- 500点問題
- こんなに制約条件が多い問題は初めてでかなり混乱しました。状態空間が高々2^14通りだからダイクストラでやってみるか、という方針が立つまで40分。そこからコード書こうとするもとても間に合わず、提出できませんでした。明日じっくりやる。
- 1000点問題
- 500点問題がさっぱりさっぱりだったので開いてみた。こちらのほうが見た目単純そうな問題です。二部グラフのマッチングさえできれば解けるのかな、たぶん。
Workspace-Gold間でグラフを作って最大マッチ数を調べる。Workspace-Silver間でも同じことをして、両者の最小値をとるとよい？ でも名前は分かっても具体的なアルゴリズムは知らないので書けない…。
Challenge Phase
- 250点問題:みんなコードがシンプルなのでつっこみどころがない
- 500点問題:みんなコードが複雑なので読めたもんじゃない
というわけで、とても低調なチャレンジフェーズ。
System-Testing Phase
250点問題で落ちてる人、全体で3人しかいない…。チャレンジで落ちてる人も0人なので、提出者内での正答率が99.51%とかいう数値になってます。
500点はけっこう落ちてる。難しかったからなあ。
結果
| Level | Status | Coding Time | Score |
|---|---|---|---|
| 250 | Passed System Test | 10:23 | 221.83 |
| 500 | Compiled | 1:04:29 | 0.0 |
| 1000 | Opened | 33:42 | 0.0 |
チャレンジなし
スコア 221.83 / 676人中214位 / レーティング 1375→1488
今回は500点問題が難しくて全体的にスコアが低めだったので、250点問題だけ解けたのでもずいぶん上がりました。イエローコーダーへの再チャレンジが狙える位置だ。
SRM423は平日朝の開催なので、1回休みです。次回の参加は半月後か…。禁断症状出そうだな。
