2010-02-14

■ [SRM][本番]SRM461 16:22

2010-02-13 26:00-（JST）

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

残念なマッチが続く

Level	タイトル	試合中	あとで	ひとこと
DIV1 300	ColoringRectangle	AC 26min	-	greedy、コピペミスで時間ロス
DIV1 500	BuildingCities	TLE 27min	済	ダイクストラ、最適化不足
DIV1 950	FencingGarden	Opened	-

• Coding
  • 300
    • 大きい円から使っていけば良いだけでは…
    • 300だから何かトラップがあるんじゃないかと考えるも思いつかない
    • 仕方ない書くか
    • 赤から使う場合と青から使う場合と
    • サンプル合わない
    • デバッグするとしょうもないコピペミス発見
      • 今回みたいに、よくコピペで同じようなコードを二回書いちゃうことがあるけど、これ良くないスタイル
      • 多少めんどくても共通化してまとめるべきだ
    • サブミット
    • 問題の難易度的には250だと思う
  • 500
    • グラフっぽいなあ。
    • 出発点から始めて、街を作る数が少なくて済むところへ順次移動していくようなイメージ
    • 街と街との間を直接移動するときに新しい街を作らないといけない数を辺の重みとして、始点から終点までの最短距離を求めればよい、ということはダイクストラ
    • しかし移動距離の制約もあるので、もう一工夫必要
    • （現在位置、新しく街を作った数）の組をノードとして、状態ごとにそこに至るまでの最短移動距離を覚えておくとよいか。状態数は 50*数千 だからいけそう
    • 書けた、がサンプル合わない
    • ああ、maxTravelって通過する街の数だと思ってたけど、そうじゃなくて移動したユークリッド距離か。最高2000だからそりゃそうだ
    • 書き直すとサンプル合った
    • サブミット
    • ランダム最大ケースも一瞬で終わるからまぁ大丈夫かな？
  • 950
    • 開いたはいいが残り15分だし読解に時間がかかりそうなのでやめた
  • 300に戻ってトラップがないかを考える
    • 思いつかず
• Challenge
  • 300で、円の直径が高さ以上かどうかを確認せずに計算しているせいでsqrt()に負数を渡してる人がいる
  • チャレンジしてみたら失敗
  • 後で赤い人が「C++ではsqrt()に負を渡しても例外は出ずにNaNが返るだけだよ。自分もたまにチャレンジする人へのトラップとして入れる」と解説してた。むきー
  • てかそれJavaでもそうじゃないか…。言語仕様に関わるとこへのチャレンジは確認してからやらないと
• System Test
  • 300は通った
  • 500は落ちた
    • TLEでした。ランダム最大ケースと最悪ケースとの差はでかい
    • ほんのちょっとした最適化で通りました

• スコア：184.17 + 0.00 + 0.00 + (50*0-25*1) = 159.17
• 順位：276位/690人
• レート：1705→1726

500通ってたら自己最高順位だったのにー。