Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2012-01-09

SRM 527 practice

23:38

opened x opened: 0.00 pts. 自分の実力を認める展開。あるいはpracticeでよかったともいいます。

275

なぜか貪欲でいけると思い込みました。手元で貪欲法を作ってはその反例を作るを繰り返して時間を潰しました。

やっている最中にノートPCが電源トラブル?で電源が落ちました。再起動してから冷静になって次に。

25分くらいかけてました。本番ならもっと早く動いているはずです。心配だし。

Systest後、ブログにあるDPという記述を見てやっと解法に気づく。気づけば簡単でした。

木の端の頂点をひとつ除いたものを考えます。名前が有りそうですが忘れたのでブランチとでもいいましょう。1頂点だけ使ったブランチは、その唯一の頂点の次数は1です。2頂点のブランチは次数はそれぞれ1, 2です。

max_score[頂点数][ブランチ数]に、N頂点使ってブランチをb個作った時のスコアの最大値を保持します。これを下から順に埋めていきます。

これでDPになりました。

450

  • 辞書順なので頭から探索するに違いない。
  • 探索の途中でも条件を満たすかどうか調べたほうがいい。
  • 条件を満たすかどうかは、二部グラフがfull matchするかどうか確認すればよい。

手元に2部グラフのコードが見当たらないのでゴリゴリ書きました。Edmonds-Karpで。サンプル通ったので提出。

しかしなぜかTLE Systest Failed。調べたところ大きなグラフで0と?としかない入力でした。手元では600 ms程度で実行できているのですが。

1050

残り時間が殆ど無かったので眺めるだけでした。後で解きます。

 |