2011-02-01

■ [SRM]SRM496 01:03

2011-02-01 21:00-（JST）

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

Level	タイトル	試合中	あとで	ひとこと
250	ColoredStrokes	AC 5min	-	早解き対決
500	OneDimensionalBalls	AC 40min	-	また汚いコードを書いてしまった
950	YetAnotherHamiltonianPath	Opened	-	賢い解き方をしてる人の解法が論証できてない

• Coding
  • 250
    • これは赤と青を独立にしてやるだけではないかー
    • こんな完全早解き対決は久々
    • 途中ちょっと無駄なことをしようとしてしまっていまひとつ
  • 500
    • まずは速度を固定したら二部グラフになるなーと思う
    • なので最大50回二部マッチングして、それぞれN個マッチするかを見れば良い？
    • いや1通りの速度でも複数のマッチングの方法がありえるから駄目だ。パターン数を数えないといけない
    • DP? とか2-SAT? とかいろいろ考え出してよく分からなくなってきたので
    • ノートに数直線を書いてサンプルのケースをじっくり見てみると、
    • 速度をVとすると、位置を mod V で分類した互いに干渉しないレーンに分解可能なことがわかる
      • SRM487 DIV1 Easy BunnyComputerと同じような考え方
    • グラフがひと繋がりになった部分はおのおの独立に考えてよくて、
      • firstがX個とsecondがX+1個でマッチしている場合（／＼／＼／＼ 型)ではX+1通り
      • firstがX個とsecondがX個でマッチしている場合（／＼／＼／ 型)では1通り
      • firstがX個とsecondがX-1個でマッチしている場合（＼／＼／ 型)では0通り
    • こいつらを掛け合わせると、その速度で何通りのパターンが可能かが出せる
    • あとは可能な速度を最大50通り全部調べる
    • いくつかバグらせてちょっと時間かかったけど提出
    • 最初にちょっと二部マッチングを書こうとしたときの名残に引きずられて汚いコードだ…
  • 950
    • ソートして貪欲にくっつけていけば良さそうだけども…Hardがそんな簡単なはずが
    • 最初と最後をどう扱ったらいいかうまく考えられなかった
    • サンプルが単純なgreedyでも通るものばかりなので落とせるケースを準備しておく
• Challenge
  • 950で怪しげなgreedyの人がいる。けど用意しておいたのでは落ちなさそう
  • テストケースを考えて投げる→ミスった→もう一度よく考えて投げる→落とせた
  • もう1人似たようなのがあったけど時間がなくて間に合わず
• System Test
  • 通った

結果

• スコア：240.26 + 240.03 + 0.00 + (50*1-25*1) = 505.29
• 順位：77位/691人
• レート：2334 -> 2348

3回連続70位台。highestを4だけ更新 & volatility最低を更新