Hatena::Grouptopcoder

hotpepsiの練習帳

2016-12-23

SRM 693

23:54

https://competitiveprogramming.info/topcoder/srm/round/16748/div/1

Div1 Easy (250) BiconnectedDiv1

問題

  • 任意の頂点u,vについて、任意の辺eを取り除いてもuからvに到達可能なグラフを、2辺連結グラフと呼ぶ
  • N個の頂点が与えられる
  • 頂点iとi+1には重みw1[i]の辺がある
  • 頂点iとi+2には重みw2[i]の辺がある
  • 2辺連結グラフを維持しながら、辺を除去するとき、重みの合計の最小値を求める

方針

  • DPでできそう
  • ある頂点の状態として、入ってくる辺と、出ていく辺と、その頂点を追い越して次の頂点に接続している辺がある
  • 制約条件は、必ず2辺以上を持つこと
  • 最初の頂点は必ず2辺が出ていく(自分を追い越す辺はない)
  • 最後の頂点は必ず2辺が入る(自分を追い越す辺はない)
  • dp[頂点][辺の状態]=コスト として、辺をつないでいない状態からスタートし、1頂点ずつ処理していく
  • 自分に2辺接続していたら(2つ前か一つ前の頂点から辺が出ていたら)、出ていく辺の本数は任意
  • 自分に1辺接続していたら、1または2本の辺を出す
  • 前の頂点から辺がなければ、2本の辺を出す
  • Passed System Test
  • (終了後)
  • 複数の場合をまとめた
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_693/BiconnectedDiv1.cpp

結果

o-- 99.77pt 160th/373 rating 1429 -> 1478 (+49)

DP書くのに1時間くらいかかったが、4連続0点から脱出できた。


http://togetter.com/li/991988

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20161223