Hatena::Grouptopcoder

Tayama@TopCoder

 | 

2011-05-12

SRM506 Div1

00:44

やっぱりライブラリって大切だよね。


250: SlimeXSlimesCity

  • しばらく退席してて、戻ったときには始まってた。
    • 250 - 600 - 1000 だと...?
      • こないだの 300 があれだけ難しかったのだから、600とか無理ゲーに違いない。250早解きだけを目指そう。
        • Division Summaryによるとスピードレースっぽい。
  • 読んだ。
    • 私は読んで一瞬で解法が浮かばないと、読み間違いがないか探し (大抵ないけど) 、次にサンプルをじっくり読んで考えることが多いのですが。
    • 今日はスピードレースなので解法は自明なはず!
  • 普通に考えて、街 i が最後に残るかどうかそれぞれ判定できればよくて。
  • 最後に残したければ、街はだんだん大きくなってくんだから、小さい街からマージしてけばよくて。
    • はい自明でした。
  • 書いた。サンプル合わない。long longにしたらでてきた。
  • Arenaでコンパイルしたけどなかなか終わらない。一回Request Timed Out食らったりして、3回目で通った。submit.
  • 242点ぐらい。うん、悪くないかな。

600: SlimeXGrandSlimeAuto

  • 濃厚に匂い立つDP臭。
    • でも状態数が 2^50 ぐらいから落ちない...。
  • ...
  • distinct[i] - distinct[i+1] 間の移動に2台以上の車を使うことってどう見てもないですよね。
    • distinct[i] - distinct[i+1] の移動に cars[j] を使った時のコストは簡単に求まって。
    • それぞれの区間にどれかの車を割り当てて、コストを最小化。
  • ...ハンガリアンマッチング!?
    • んなもの書いたことない!ついでに最小費用流も勉強したことがない!
      • ↑ 日 本 の 非 常 識
  • Spaghetti Sourceから拝借して頑張ってみたけどダメでした。

Challenge Phase

  • 250を O(N) でやってる人がいたけどよく見たら正しそうだった。実際 System Test に通ってた。
  • 600でハンガリアンマッチングの行列のサイズ足りてない人に気づかなかったのは失態だったと思う。

System Test

  • 250通って140位ぐらい。1762 -> 1803
  • 1800代復帰。このまま2000ぐらいまで行きたいな。
  • 最小費用流もあとでちゃんと勉強しておこう...。
 |