Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2010-12-29

[]SRM492 00:33 はてなブックマーク - SRM492 - TopCoderの学習のお時間

2010-12-29 11:00-(JST

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


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

  • 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の再提出がなかったら自己最高順位だったが。まあこれからまだいくらでも機会はある

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

 |