2011-04-16

■ [SRM]SRM503 05:25

2011-04-16 25:00-（JST）

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

Level	タイトル	試合中	あとで	ひとこと
250	ToastXToast	AC 13min	-	問題文読解ゲー+greedy的発想
500	KingdomXCitiesandVillages	WA 28min	済	問題読み違えイージーミス
1000	KingdomXEmergencyStaircase	Opened	-	問題文がややこしいということだけはわかった

• Coding
  • 250
    • 問題文の理解が難しい
    • サンプルを見て推測
    • 最悪DPすればできるんだろうけどもっと簡単な規則がありそうな
    • 一瞬二部グラフとか考えてしまった。違う違う
    • どう組み合わせるのが最適か考えてみると、underの最初のやつとoverの最後以外全部を組にしといて、残ったunderの最初以外全部はoverの最後につなげてやればよくて、組み合わせを作れる場合は最大2種類あれば十分だと気づく
    • あとは簡単な場合分けすればOK
  • 500
    • やった確率だ
    • まずは、線形性から各villageを独立に考えてよい
    • 直近のcityよりも近いところにあるvillageを集めて、道を作る先が一番近いvillageになる確率、2番目に近いvillageになる確率…を計算して足していく
    • 確率の計算は、まあ普通の場合の数の問題
    • 提出した後にサンプル弱くて不安だったのでvillageが4つの場合を手計算で確かめる
    • うわ数え間違ってる…village3つ以下の場合はたまたま間違った式でも合っちゃってた
    • 再提出
  • 1000
    • 問題文長い！
    • 読み終わった時点で残り5分
    • 閉じた
• Challenge
  • 250でサンプルで全パターン網羅されてないので不等号間違いとかのイージーミスを探したけどなかった（いたけど先に落とされてたみたい）
  • 500で他の人の解答を見てマンハッタン距離とユークリッド距離を取り違えていたことに気づく
    • 明らかなミスなのになかなか落とされないなーと見ていたら落とされた
• System Test
  • 250は通った

結果

• スコア：215.95 + 0.00 + 0.00 + (50*0-25*0) = 215.95
• 順位：211位/793人
• レート：2253 -> 2225

500はマンハッタン距離でやってたところをユークリッド距離に修正したら通った。残念すぎる