2009-12-23

■ [SRM][本番]SRM456 13:41

2009-12-23 11:00-（JST）

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

今年最後のSRM。

Level	タイトル	試合中	あとで	感想
DIV1 250	SilverDistance	AC 15min	-	碁盤目系シミュレーション。 盤面を市松模様に塗り分ける。始点と終点が同じ色だったら、Max(dx, dy)が答え。 違う色だったら、終点の1つ下のマスに行ってから上に1マス移動する (dx-dy)%2==1 というコードを書いてはまってた。剰余は負になるのか…
DIV1 450	CutSticks	AC 45min	-	二分探索。 前にgreedyで解く似た問題があったけど、サイズ10億なのでO(√N)かO(logN)のはず+返値が小数→二分探索？　という流れ 解候補となる棒の長さに対する成否の単調性が疑問になったが、 初期状態から指定の長さの棒をK本切り出せるか？　と考えると大丈夫だと確信できた 答えが1未満になることの見落とし + イージーミスで2回再提出… 以前の教訓通り二分探索のループの回数は定数で
DIV1 1050	FunctionalEquation	Opened	-	数学。眺めただけ

• Challenge ＆ System Test
  • 再提出しちゃったときのセオリー通り、自分と同じミスをしている人を狙う
    • 二分探索のコードで left = 1.0 とか書いてあるやつ
  • みんな二分探索の下限0だ…　そりゃそうか
  • と思ったら赤い人のコードに "0.01" という怪しげな値が見える
  • 慎重に読んでからチャレンジ。成功。
  • 250は場合分けでやっている人たちがいたので、何人かは落ちるだろうと思ったが時間内では読めない
  • 数人システムテストで250落ちてた
    • ちょっと見たところ剰余が負になるパターンみたい。これは覚えておこう

• スコア：199.79 + 135.00 + 0.00 + (50*1-25*0) = 384.79
• 順位：112位/516人
• レート：1920→1957

レーティングがバブル期。