2011-01-24

■ [SRM]SRM494 23:18

2011-01-22 26:00-（JST）

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

得手不得手がはっきりと

Level	タイトル	試合中	あとで	ひとこと
250	Painting	AC 38min	-	苦手ジャンル：計算量見積もり
500	AlternatingLane	AC 21min	-	得意ジャンル：期待値の線形性
1000	KnightsOut	Opened	-	むずい

• Coding
  • 250
    • O(N^5)では駄目だと思ってしまって頑張ってO(N^4)解法を書いちゃいました
    • "TopCoderの問題がこんなにやるだけのはずがない"という予断にやられた
  • 500
    • よっしゃ確率来た
    • 木を取り除く場合と取り除かない場合の場合分けが厄介
    • どういう戦略が最適なのかを具体例から考えてみると
    • たとえば [4,3,1,5]と並んでいたとき、
      • 4から直接5に行くよりいったん下がってから上がった方が良い
      • 4→3→5よりも4→1→5のほうが良い、つまり連続している下りは一番先にある一番深いやつを使うべき
      • けどこれは、坂の途中にあるのも含めて4→3→1→5と使うのと同じことになる
      • など考えて、結局上り下りが交互だとか木を取り除くとかは考えずに次にある木を全部使えばいいのではという洞察を得た
    • それと期待値の線形性からそれぞれの位置は独立に考えていい
    • あとは計算するだけ
    • 一番の得意分野にしては早くなかったがまあ十分
• Challenge
  • 250で連続する黒の長さの最小値を返している人がいたが反例をすぐ考えつけなかったので放置
  • 部屋内で落ちたのはほぼそれだけだったからじっくり考えておくべきだった
  • 250はみんなO(N^5)で書いててむきーとなった
• System Test
  • 通った

結果

• スコア：123.02 + 344.95 + 0.00 + (50*0-25*0) = 467.97
• 順位：73位/731人
• レート：2296 -> 2322

さすがにもう2桁でもそんなに上がらない。50位以内を目標にするべきなくらいか