■ [本番][TCO]TCO09 Algo Round2
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=13760&rm=300644
720人→300人。だいたいSRMのDIV1と同じかわずかに難しいくらい?
Level | タイトル | 試合中 | あとで | 感想 |
---|---|---|---|---|
900 | ConnectingAirports | 読んだ | - | Graph。最大流でOK? でも最大流書いたことない… 問題を読んだ時点で30分残ってたから、コードを検索してきて書くことはできそうだったけど、 「解が複数のときは辞書順最小のものを返す」で失敗しそうなのでやめた。600に集中することに |
600 | ExtendableTriangles | 途中 | - | 幾何。ナイーブにやるとO(N^6)なのでだめ。 extendableなやつではなくnon-extendableなものを数えるとオーダー小さくなりそう、と考える しかしnon-extendableである条件をコードに落とせない。幾何問題は弱いなあ |
250 | PlaneFractal | ○ 31min | - | Math。問題を把握するのにすこし手こずる。 各位置の座標をN進数にして、各桁がまんなかKの範囲内かを見る。サイズが小さいので総当たりでOK。 読めてしまえば解法はすぐ見えたけど書くのが遅かった |
- Challenge
- Division Summaryによると、ふたつ落とせば通過できるくらい
- 1000でTLEがありそうだけど、たぶん競争率が高そうだから250を狙う
- サンプルに s=0 の場合がなかったので、見落としている人がいないかと探す
- チャレンジフェーズ終了5秒後に発見…
- s=0 で落ちるのが二人いたので、両方とも素早く発見できていれば通過できてたのか…
- 途中600に浮気したりしてたのがいけなかった
- 順位:458位/674人 Round2敗退
- レート:1817 → 1790
いかにも「もう少しがんばりましょう」な結果でした。