Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-09-30

StampsCollection

| 02:14 | StampsCollection - TopCoder煮ブログ を含むブックマーク はてなブックマーク - StampsCollection - TopCoder煮ブログ

DIV1 むずいの続き。

こないだ挫折した SRM418 DIV1 Level2 の StampsCollection の答えを読解。

  • グラフに置き換える
    • demand は節点
    • price は節点の重み
    • 同じ stamp を欲しがってる節点同士を枝で結ぶ

3) の例だとこんな感じ。

 ┌─┐    ┌─┐    ┌─┐
 │5│----│9│----│5│
 └─┘    └─┘    └─┘

誰が購入するかを決定することは、「枝を共有しないような節点を選ぶ」と等価になる。収入を最大化するということは、重みを最大化するように選ぶこととなる。つまり、これは最大次数が2の wikipedia:最大独立集合問題 だ、と。

上の例だと、左の2つの節点(5 と 9)を選択してしまうと、枝(Stamp 0)を2人が欲しがってしまうので NG。9(真ん中の節点)もしくは、5+5(両端の節点) のいずれかで、答えは10となる。

んー、言われれば納得するが思いつかない…。

で、解法。

  1. 深さ優先探索して節点をグループ分け
  2. 各グループについて、最大値を求める。
    • 最大次数2なので、一本道もしくは閉路のどちらか
    • 奇数番目、偶数番目だけを選んだときの最大値を求めればよし
    • ただし、閉路のときには少し気をつける