2011-01-13

■ [SRM]SRM493 00:04

2011-01-13 11:00-（JST）

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

Level	タイトル	試合中	あとで	ひとこと
300	StonesGame	AC 40min	-	誤読
450	AmoebaCode	Opened	-	苦手ジャンル：計算量見積もり
1000	AmoebaDivOne	UnOpened	-	-

• Coding
  • 300
    • 選んだ範囲の白黒を反転させるのだと誤読して25分くらい違う問題を解いてた…
      • これはこれで面白い問題になってた
    • 1手目で届く場合は先手の勝ち
    • 1手目でどこへ動かしても2手目で届かせられる場合は後手の勝ち
    • それ以外は引き分け
      • 後手は先手の真似をして無限ループにしておいたら負けることはない
      • そうすると先手は勝つ目がないのだから同じように相手の真似をして引き分けに持ち込むことになる
    • 1手で移動できる場所はサイズ100万だから全部列挙すればよい
  • 450
    • かなりのDP臭
    • 現在位置のK-1個前までを全部覚えてやったらとりあえず出せそうだけど
    • 計算量 7^6*50*7=4000万くらい か−。大丈夫だろうけどそれが想定解なのだろうか…
    • もっと良い方法を考えてみるがわからないので最初の方法で書き始める
    • 時間切れ
    • これがmediumなのは実装が面倒だから？
• Challenge
  • 300で移動可能かどうかを調べるときに偶奇を見ていない人があったので落とす
  • もう1個同じようなのがあったが失敗
    • 他の人が似たケースで落としてたからたまたま自分のケースでは通っちゃったのか
    • 1回チャレンジ成功して正スコアが確定した後だったので、しっかり検証せずに投げたのは戦略としては問題ないつもり
  • 450でgreedyにやってる人がいたので落とせるケースを考えているうちに他の人に落とされた
• System Test
  • 300は通った

結果

• スコア：144.37 + 0.0 + 0.00 + (50*1-25*1) = 169.37
• 順位：118位/530人
• レート：2317 -> 2296

盛大なミスをしたが大崩れしなかったのでまあよし。

こういうときも、ゆっくりでいいので慌てず1問取っておくとかなり安定します（ターゲット狙うような位置だったら駄目だけど）。