Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2009-03-14

[][]TCO09 Algo Round2 03:05 はてなブックマーク - TCO09 Algo Round2 - TopCoderの学習のお時間

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=13760&rm=300644

720人→300人。だいたいSRMのDIV1と同じかわずかに難しいくらい?

Levelタイトル試合中あとで感想
900ConnectingAirports読んだ-Graph。最大流でOK? でも最大流書いたことない…
問題を読んだ時点で30分残ってたから、コードを検索してきて書くことはできそうだったけど、
「解が複数のときは辞書順最小のものを返す」で失敗しそうなのでやめた。600に集中することに
600ExtendableTriangles途中-幾何。ナイーブにやるとO(N^6)なのでだめ。
extendableなやつではなくnon-extendableなものを数えるとオーダー小さくなりそう、と考える
しかしnon-extendableである条件をコードに落とせない。幾何問題は弱いなあ
250PlaneFractal○ 31min-Math。問題を把握するのにすこし手こずる。
各位置の座標をN進数にして、各桁がまんなかKの範囲内かを見る。サイズが小さいので総当たりでOK。
読めてしまえば解法はすぐ見えたけど書くのが遅かった

  • Challenge
    • Division Summaryによると、ふたつ落とせば通過できるくらい
    • 1000でTLEがありそうだけど、たぶん競争率が高そうだから250を狙う
    • サンプルに s=0 の場合がなかったので、見落としている人がいないかと探す
    • チャレンジフェーズ終了5秒後に発見…
    • s=0 で落ちるのが二人いたので、両方とも素早く発見できていれば通過できてたのか…
    • 途中600に浮気したりしてたのがいけなかった

  • 順位:458位/674人 Round2敗退
  • レート:1817 → 1790

いかにも「もう少しがんばりましょう」な結果でした。

 |