Hatena::Grouptopcoder

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

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

 | 

2010-01-16

[][]SRM458 17:46 はてなブックマーク - SRM458 - TopCoderの学習のお時間

2010-01-14 25:00-(JST

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

mathyなセット


Levelタイトル試合中あとでひとこと
DIV1 250BouncingBallsAC 9min-数学、シミュレーションは不要
DIV1 450NewCoinsAC 42min 1度再提出-DFS+枝刈り。DPの方が効率的
DIV1 900ModuloFourDivisorOpened-整数論。他の人の回答も見たが未理解
  • Coding
    • 250
      • 玉の動きを全部シミュレーションしないといけない? だとすると250にしては複雑
      • サンプルに58が入ってることもあるし、もっと数学的に綺麗に解けるんじゃないか
      • 玉の跳ね返りは無視して貫通すると思えばよいことに気づく
      • すると期待値は各玉ペアについて独立に計算してよくて、O(N^2)でいける
      • 2つの玉が衝突するのは全移動方向パターンのうち1/4なので、距離2T以下のペアが一つあるごとに期待値を+0.25する
      • 他の人のコードを見ると、移動方向パターンを2^N種類全部調べるO(2^N*N^2)の回答が多かった。自分は、「玉は貫通すると見なしてよい」→「各ペアを独立に計算してよい」というのは前者に気づいてすぐ後者に到達したのだけど、なぜ独立でよいか証明しろと言われたらすっきりした説明はすぐには難しそう。数学的直感とは不思議なものです
    • 450
      • また数学っぽい問題
      • 最大10万と問題サイズがあまり大きくなかったので、次に大きいコインを何倍にするかでDFS探索した
      • やはり大きいケースでTLE
      • 倍率は素数に限定して良いことに気づいたのでそうしてみると、ランダムな最大ケースが1.5秒。うーん微妙
      • ちょっとした枝刈りを入れてみたら倍くらいには速くなったので不安がありつつも提出
    • 900
      • とりあえず問題読んで残り30分くらい。取り組むかどうか迷い、450が不安だったのでテストに専念
    • 450をテスト
      • off-by-oneエラーを発見して再提出。120点ほど損してしまったが見つけられてよかった
  • Challenge
    • 450のコードは一通り見たが皆さんいろんなことをやってるみたいで読めない
    • 250でひとつ、 if (i & 1<<j) みたいな、それ優先順位間違えてるだろというコードを発見 【追記】勘違いでした
      • しかし落ちるケースは見つけられなかった
      • というかその回答システムテストも通ってた。たまたまか…
  • System Test
    • 250も450も通った
      • Practiceで試してみると、450はどのテストケースも1秒以内で終わっていました
    • 部屋内の250は全部通ってた
  • スコア:227.20 + 165.10 + 0.00 + (50*0-25*0) = 392.30
  • 順位:119位/631人
  • レート:1819→1887

ひとまず1800台は保ちたい。

今年の目標は Algo+Marathon >= 4200 くらいかな

codercoder2010/01/17 00:45>>if (i & 1<<j) みたいな、それ優先順位間違えてるだろ
優先順位はシフトの方が高いみたいですよ
http://www9.plala.or.jp/sgwr-t/c/sec14.html

tomeruntomerun2010/01/17 01:18あれ、そうですね。勘違いでした。
演算子の優先度一覧を確認したとき、単項のアドレス演算子&とビット演算の&を混同していたようです

 |