2010-12-29

■ [SRM]SRM492 00:33

2010-12-29 11:00-（JST）

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

Level	タイトル	試合中	あとで	ひとこと
250	TimeTravellingGardener	AC 20min	-	誤差の見積もりミスして無駄に再提出
550	TimeTravellingTour	AC 41min	-	雑なコードだった
1000	TimeTravellingGogo	Opened	-	ざっと見ただけ

• Coding
  • 250
    • 全部調べろ問題
    • doubleで処理するのは嫌だが整数だけで扱う方法がすぐ出てこなかったのでEPSを使う
    • サンプル合わない。端が地面よりも下になっちゃいけないのね
    • 端を0にするケースも付け加え
      • （もうこの場合は1つを通るケースしかあり得ないのだから return N-1; でよかった）
    • 提出
    • EPS=1e-7としていたけれどなぜか精度が足りない気がしてしまって1e-9にして再提出
      • 木の数50*隣同士の距離1000*高さ1000=5*10^7だ!　とか思ってた。最後の*1000は関係ない
  • 550
    • 経路を覚えておく探索のような方法では計算量大きすぎて駄目
    • いろんな経路の取り方が考えられるが、サンプルを見たところ戻れる場合はいつも戻るというのでよさそう
    • どこかの町をベースキャンプにして、ある町に行ったらタイムトラベルで戻ってくる、そして次の町へ行ってまた戻ってくる、というのが基本的な行動
    • ただし、訪れる町のうちある範囲の町が全部同じ方角にあるのだったら、そちらに進んだ所にある町を新しくベースキャンプとした方が良い
    • というわけでdp[town][start][end]（=townを起点としてstart番目からend番目の町を訪れる最小コスト） でDPする
    • ワーシャルフロイドで全町間の最短距離を出すところでミスっていてサンプルが合わない…時間ロス
    • たどれない場合に-1を返せていなかったのでアドホックに修正。けっこうひどいコードを書いてしまった
  • 1000
    • 問題文を眺めただけ
• Challenge
  • 何もできない
• System Test
  • 550は落ちると思っていたが通ってた

結果

• スコア：151.40 + 261.52 + 0.00 + (50*0-25*0) = 412.92
• 順位：26位/549人
• レート：2244 -> 2317

250の再提出がなかったら自己最高順位だったが。まあこれからまだいくらでも機会はある

直線のどちら側にあるかは外積の符号で見ると整数だけでいけるのだった。幾何はコンテスト本番以外では避けてるのでこういうのがすぐ思いつかなくていかんなあ