2010-01-16

■ [SRM][本番]SRM458 17:46

2010-01-14 25:00-（JST）

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

mathyなセット

Level	タイトル	試合中	あとで	ひとこと
DIV1 250	BouncingBalls	AC 9min	-	数学、シミュレーションは不要
DIV1 450	NewCoins	AC 42min 1度再提出	-	DFS+枝刈り。DPの方が効率的
DIV1 900	ModuloFourDivisor	Opened	-	整数論。他の人の回答も見たが未理解

• 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< みたいな、それ優先順位間違えてるだろというコードを発見 【追記】勘違いでした
    • しかし落ちるケースは見つけられなかった
    • というかその回答システムテストも通ってた。たまたまか…
• 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 くらいかな