2009-11-26

■ [SRM][本番]SRM453.5 00:30 はてなブックマーク - SRM453.5 - TopCoderの学習のお時間

2009-11-25 25:00-（JST）

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

前回トラブルの分の埋め合わせ的マッチ。

Level タイトル 試合中 あとで 感想
DIV1 250 MazeMaker AC 11min - BFS
ただやるだけの実装問題。Easyはこのくらいの軽さで良いですね。
なんかEclipseの設定が狂って補完が効かなくなってた。ちょっと時間ロス
DIV1 450 PlanarGraphShop AC 22min - グラフ+BFS（またはDP）
平面グラフでの辺の最大個数がわからん→教えてインターネット！　後はやるだけ
デバッグしてたらEclipseが暴走して固まってしまい、だいぶ時間ロス
DIV1 1000 TheAlmostLuckyNumbers Opened - 整数
包除原理でいいのか…。LuckyNumberが2000個くらいだから計算量2^2000だと思ったが、
何個か掛けるとすぐ最大値超えるので大丈夫、と

  • Challenge
    • 1000を諦めてDivision Summaryなどだらだら眺めていたら、けっこう450の再提出が行われていること発見。レート上位の人もだいぶやってた
    • 何かトラップがあるのかと問題を読み返して、平面グラフの辺が交差してはいけないことを見落とす人がいるかもなぁと気づく
    • そこを狙えるテストケース作成
    • チャレンジフェーズ開始してすぐ、450を再提出していない人の中で（ここ重要）レートが低い人から順に見ていく
      • 再提出しているかどうかは、個々のハンドル表示を右クリック→History で確かめられます
    • 開始20秒で「i <= n*(n-1)/2」のようなコード片が目に入ったのですぐさま撃墜
    • 250も一通り見てみたけど落ちそうなものはなく。実際、部屋で提出した全員が通っていた
    • 450で1人システムテスト落ちの人がいた。怪しげなコードだなぁと思った記憶はあるので、250に向かわずじっくり読んでいれば落とせたかも
  • スコア：218.12 + 298.23 + 0.00 + (50*1-25*0) = 566.35
  • 順位：117位/632人
  • レート：1717→1799

自己ベスト（1869）が狙えるくらいまで戻ってきたぞー