Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-30SRM356 (Practice)

SRM 356 MarriageProblemRevised

|  SRM 356 MarriageProblemRevised - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 356 MarriageProblemRevised - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6608

  • 二部構造が見え見えになってるが、マッチングでは解けなさそう
    • 制約が緩いしDPしちゃおう
  • でも、少なくとも [男x12が結婚したか][女x12が結婚したか] という状態が必要だから・・・
    • (2^12) ^ 2 = 16M
    • メモリが足りなくなるかも・・・
  • ダイクストラを実装したらサンプル合った。
    • 他に方法が思いつかないのでそのまま出してしまった。