Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-28ARC003

ARC003 D シャッフル席替え

|  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  ARC003 D シャッフル席替え - hama_DU@TopCoderへの道

  • これは難しそう・・・
  • 制約の小ささから、bitDP的なことができるのではと思ってみる
    • dp[K][P] : K回席替えした時、禁止パターンの出現組合せがPになってる確率
    • でも、更新式が思い浮かばない。
    • 紙に書いてみても、
  • 素直に順列を全探索か?
    • 制限時間10秒あるし・・・
  • 書いてる途中にコンテスト終わった

コンテスト後

  • 答えの誤差が 0.002 まで許されることから、モンテカルロ法が使えるらしい。
    • 実際にランダムにK回席替えをして、禁止パターンになってるかどうか調べるという実験をする。
    • 成功数 / 試行回数 が答え
  • 制限時間ギリギリまで実験するコードを書いたら通った。