Hatena::Grouptopcoder

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

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

 | 

2010-11-14

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

2010-10-26 25:00-(JST

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

探索の計算量見積もりが弱いことを再確認した回

Levelタイトル試合中あとでひとこと
300OneRegisterAC 39min-点数に騙され
450QuickSortAC 30min-無理やり数学的に
1000BatmanAndRobinOpened--

  • Coding
    • 300
      • えー幅優先するだけでいいの?
      • なるほど単純にやったら計算量大きいのか。300だしなあ(←勘違い)
      • 逆から考えると計算量押さえられるのかな?
      • 辞書順最小を出すための場合分けの泥沼にはまる
      • 部屋の様子を見ると青い人も続々提出している
      • 初回に / 使うの以外では1回の操作で2倍か2乗にしかならないから計算量は全く無問題でした
      • 何でこれ300なの…
    • 450
      • 出た期待値の線形性(好物)
      • 反転数でも数えればよいのかと思ったが違った
      • DP的解法も考えたがすっきりまとめられない
      • 結局、次のように考えて期待値の線形性を使って解いた
        • まず、具体的な数値は関係なくて大きさの順番だけが問題なので、入力を0〜N-1のPermutationに置き換える
        • i番目とj番目の大小が反転しているとき、i番目をpivotに選ぶことによって反転が解消する確率を考えると
        • L[j]〜L[i] の (L[i]-L[j]+1) 個の数の中からL[i]が最初にpivotとして使われる場合なので1.0/(L[i]-L[j]+1)
        • これをすべてのi,jの組について足し合わせる
  • Challenge
    • 300のコードが多彩でいろいろ見ていたら、yeharaさんのコードが幅優先ではなく深さ優先みたいになっていたので撃墜
  • System Test
    • 300も450も通った

結果

  • スコア:144.98 + 255.34 + 0.00 + (50*1-25*0) = 450.32
  • 順位:160位/721人
  • レート:2288 -> 2266

この内容でこれだけ踏みとどまれたのは及第点

 |