Hatena::Grouptopcoder

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

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

 | 

2009-12-23

[][]SRM456 13:41 はてなブックマーク - SRM456 - TopCoderの学習のお時間

2009-12-23 11:00-(JST

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

今年最後のSRM


Levelタイトル試合中あとで感想
DIV1 250SilverDistanceAC 15min-碁盤目系シミュレーション。
盤面を市松模様に塗り分ける。始点と終点が同じ色だったら、Max(dx, dy)が答え。
違う色だったら、終点の1つ下のマスに行ってから上に1マス移動する
(dx-dy)%2==1 というコードを書いてはまってた。剰余は負になるのか…
DIV1 450CutSticksAC 45min-二分探索。
前にgreedyで解く似た問題があったけど、サイズ10億なのでO(√N)かO(logN)のはず+返値が小数→二分探索? という流れ
解候補となる棒の長さに対する成否の単調性が疑問になったが、
初期状態から指定の長さの棒をK本切り出せるか? と考えると大丈夫だと確信できた
答えが1未満になることの見落とし + イージーミスで2回再提出…
以前の教訓通り二分探索のループの回数は定数で
DIV1 1050FunctionalEquationOpened-数学。眺めただけ

  • Challenge & System Test
    • 再提出しちゃったときのセオリー通り、自分と同じミスをしている人を狙う
      • 二分探索のコードで left = 1.0 とか書いてあるやつ
    • みんな二分探索の下限0だ… そりゃそうか
    • と思ったら赤い人のコードに "0.01" という怪しげな値が見える
    • 慎重に読んでからチャレンジ。成功。
    • 250は場合分けでやっている人たちがいたので、何人かは落ちるだろうと思ったが時間内では読めない
    • 数人システムテストで250落ちてた
      • ちょっと見たところ剰余が負になるパターンみたい。これは覚えておこう

  • スコア:199.79 + 135.00 + 0.00 + (50*1-25*0) = 384.79
  • 順位:112位/516人
  • レート:1920→1957

レーティングがバブル期。

 |