2010-06-18

■ [SRM][本番]SRM473 20:36

2010-06-18 10:00-（JST）

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

平日午前中。

Level	タイトル	試合中	あとで	ひとこと
DIV1 250	SequenceOfCommands	WA	-	TopCoder歴の中で過去最大のへぼいミス
DIV1 500	RightTriangle	AC 7min	-	正解率を見るとこの位が500の適正難易度なのか
DIV1 1000	RooksParty	Compiled	-	途中まで書いたので記念Compile

• Coding
  • 250
    • 無限遠に行かないときは、結局同じ位置でループになるからそれを調べればいい
    • 4回サイクル回せば最初と同じ向きになるので、4回通り実行し終わった後に位置が移動している⇔発散する と判定できる
      • なぜか3サイクルで元の向きに戻る可能性を考えてしまって12サイクル回してた…
    • 特に問題なく書けて一発でサンプル通った、提出
  • 500
    • 円に内接する三角形が直角三角形なのって斜辺が直径になる場合のみ、だよね…？
      • 今年の東大入試で似たのがなかったっけ
    • とりあえず、点の数が奇数ならば return 0;
    • どの位置が赤になるのかさえわかれば後は簡単
    • けれども点の数が10万なので、ナイーブにO(points^2)でやるとTLE
    • O(places + points) でやる方法を思いついた
      • まずは赤の点が重複したときに次の位置にずれるのは考えず、各位置に赤い点を重複して置いておく
      • 次に、placesを先頭から順にたどって、先に置いておいた赤の点を拾いつつ、1個ずつばら撒いていく
    • これでサンプル通った、提出
    • 500では見たことのない高い点数になった。不安…
    • とはいえコーナーケースも見つからないので次へ
  • 1000
    • しばらく問題を眺めて以下の洞察を得た
      • 同じ行・列には同じ色の駒しか置けない
      • 可能な配置に対して、その行や列の順序を入れ替えても配置可能なことは不変
      • 行・列の入れ替えを使って左上から順に色ごとにまとめていくことで、対角成分の周囲にだけ要素があるブロック行列みたいな形に変形できる
    • というわけで、色ごとに盤面の左上から順に長方形の領域に詰め込んでやって、詰め込み方ごとに行・列の並び替えが何通りあるかを足し上げると良いのではないかと考えた
    • たぶん工夫なしでやると遅いので memo[どの色まで使ったか][次の色のブロックを始めるx座標][同じくy座標] を状態空間とするメモ化DFSを書こうとした
    • しかし間に合わなかった
    • この方針で合ってるかどうかは未検証
• Challenge
  • 250をざっと見てみたけど落ちそうなポイントは見あたらない
    • と思っていたら自分の250が落とされた…！
    • コピペミスで、dyと書くべき所がdxになっていたのが原因…これはひどい
  • 500を見る
    • 赤くする点を正しく決めれてなさそうなコードを発見
    • 即興でテストケースが作れたので投げてみると落ちてくれた
    • 1つずつナイーブに調べていそうなコードがあったのでTLEするかと思って最大ケースを投げてみたが落ちなかった
      • 次に入れるべき位置を随時更新しているのを見落としていた
• System Test
  • 自分の500は通った
  • 部屋内で撃墜残しは500が1つ、どこで落ちてるのかはよくわからない

結果

• スコア：0.00 + 465.97 + 0.00 + (50*1-25*1) = 490.97
• 順位：122位/471人
• レート：1829→1875

自己最高順位が逃げていった…。また次回がんばろう。今回くらいの速さを安定して出せて変なミスを減らせれば、レーティング2000どころか赤が見えてくる

なぜか強い人が500をあまり一瞬で解けていなかったようで、あと10秒速ければ全体で最速だった http://www.topcoder.com/tc?module=ProblemDetail&rd=14155&pm=10976