Graph Theory

URL https://community.topcoder.com/stat?c=problem_statement&pm=14811 概略 有向木の頂点に石を置いていくゲームを行う．葉には無条件で置いてよい．親に置くためには，その直接の子すべてに石が置かれていなければならない．また，任意のタイミングで石を取り除くことができる．根に石を置いた時点でゲームは終了する． 各頂点には重み $w$ が付いている．石が置かれている頂点 $i$ について $W = \sum w_i$ が逐一計算され，ゲームのスコアは $\max W$ である．スコアの最小値を求める． 方針 操作を先読みしたいときにはメモ化再帰が有効です． dp[i] := iに石を置く操作をするときのスコアの最小値とします．頂点iの子がL，Rであるとき，iに石を置く操作には以下の工程が考えられます． Lに石を置く dp[L] Rに石を置く dp[R] Lに石を置く操作を一通り行った後，Rに置く操作を行う．またはその逆．これは小さい方を選択できる． min(w[L] + dp[R], w[R] + dp[L]) LとRの両方に石が置かれていて，iに石を置く w[i] + w[L] + w[R] dp[i]はこのうちの最大値を取ります．子が0, 1つの場合も同様に計算できます． [展開する] 反省 操作順を親と子の重みだけで評価できると思って時間を溶かす．そんなわけない．

URL https://community.topcoder.com/stat?c=problem_statement&pm=15257 概略 単純無向グラフ $G$ が与えられる．$G$ の橋を含まないような誘導部分グラフのうち，頂点数が最大となるものを求める． 方針 要は，$G$ から橋だけを残したグラフについての最大独立集合問題である．このグラフは明らかに森であるから，木DPが使える． 参考 制約が甘いので橋の検出にはUnionFindを使う．各辺ごとにそれを除いたグラフを構築し，端点の連結性を判定する． [展開する] 反省 本番では橋の検出までしかできなかった．最大独立集合問題であることにはなんとなく気付いていたが，名前だけが先走った．「NP困難じゃん…」 dp等の初期化も忘れずに．