Hatena::Grouptopcoder

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

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

 | 

2010-11-14

[]SRM 487 01:37 はてなブックマーク - SRM 487 - TopCoderの学習のお時間

2010-11-13 26:00-(JST

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


Levelタイトル試合中あとでひとこと
250BunnyComputerAC 8min-もっと速く書きたかった
550BunnyExamWA 21min-反例の探し方が下手だった
950BunnySequenceAC 37min-950にしては易しめか

  • Coding
    • 250
      • 絵があると理解しやすいですね
      • 少し考えるとK+1本のラインに分割して独立に扱えることがわかる
      • DPかとちょっと思ったが、もっと簡単にできる方法を思いついた
      • 偶数個だったら全部使えるし、奇数個だったら偶数番目のものどれか1つが使えないので最小のを捨てる
    • 550
      • 出た期待値の線形性(好物)
      • とりあえず選び方が存在する場合の答えは線形性からm/kで良い。多分に直感的だけど
      • 選び方が存在するかどうかは…
        • k=1,2の場合は簡単
        • 3以上の場合は選べないケースを思いつけなかった
        • 550だからそんな簡単なはずはなかろうが…
      • もし950が自分にも解答可能なレベルだったら、ここであまり粘ると逃してしまう(結果的にこの判断は正解だった)
      • とりあえずkが3以上の場合は常に条件を満たせるとして提出
    • 950
      • お、数論。これはいけるかも
      • 入力が100万なのでDP的にO(N)かデータ構造こねこねしてO(NlogN)か、てとこだろう
      • サンプルにあったm=3,n=4のケースの樹形図を書いて構造を把握
      • 「*」または「-」を、「-」がm個以上連続しないようにn-1個並べる場合の数の問題として構成できた
        • ただし 1->3->2->1 みたいに1に戻るのを禁止するため、先頭だけは「-」はm-2個までしか連続できない
      • ここまではすぐだったのだけど、これをO(N)で求める方法がわからなくて
      • 20分くらいぐちゃぐちゃ考えていたらやっとDPでいける方法が思いつけて
      • 2分前に書き上げられました
      • 他の人の解答を見たらとても短いのでもっとシンプルな考え方があったのだろう
  • Challenge
    • 550がすぐさま撃墜されていった。まあ予想通り
    • 550でm=1とかk=1,2の場合をざっと見たが落ちそうなのはなく
    • 250を読んでいく
    • 計算量がO(2^N)でTLEしそうなコードがあった。自分の950が通っている自信がなくて-25すると悲劇なのでじっくり確認していたら他の人に落とされた。仕方ない
  • System Test
    • 250も950も通った。初のHard正解

結果

  • スコア:231.36 + 0.00 + 474.56 + (50*0-25*0) = 705.92
  • 順位:30位/753人
  • レート:2266 -> 2344

highest!

でも550でk=3の反例が思いつけなかったのは反省すべき。適当にランダムに並べつつ反例を探していたけれど、問題の制約から論理的に構成していくような考え方をしないと。

 |