2008-09-20 SRM 418 TopCoder 250 N個の数からM個選ぶくじを買ったときK個以上あたっている確率を求めよという問題。N<=8なので選び方を全列挙するだけでよい。 500 次数2以下のグラフの最大重み独立集合を求めよという問題。次数2以下のグラフは孤立点か直線か円しかなくて、孤立点は単に重みを足してやればよくて、円は適当な一ノードを使うか使わない場合に分ければ直線の場合に帰着できる。 直線の場合の最大重み独立集合は端から見ていって現在のノードを使った場合と使わなかった場合の最大重みを計算していけばよい。 900 解法不明