Hatena::Grouptopcoder

TopCoder煮ブログ

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

2008-09-23

DIV1 むずい

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

練習で SRM418 DIV1 Level2 の StampsCollection を解いてみた。テストは通るんだけど、System Test が実行時間が長すぎて失敗。手元にテストを持ってきたら、確かに計算が終了しない。

正解者の答えを解析しようとがんばってるが、かなり難易度高い。恐るべし、DIV1。正答率12%、早い人でも40分近くかかってる模様。

→ (追記)SRM 418 - tsubosakaの日記 によると、「次数2以下のグラフの最大重み独立集合」という問題に帰着できるようだ。