hotpepsiの練習帳

SRM 696

09:51

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

Div1 Easy (300) Gperm

問題

• 50個の頂点がある
• 1ターンに1つずつ塗っていく
• 20本以内でM本の辺が与えられる
• 辺の両辺が塗られているとき、1ターンごとにコストが1発生する
• コストの総量の最小値を求める

方針

• わからないので適当に貪欲で書く
• Failed System Test
• (終了後)
• kmjpさんの解説を読む
• 辺が全て張ってある状態から、取り除いていく
• 各頂点に含まれる辺をbitで持っておく
• 片方の頂点が取り除かれればその辺のスコアが加算されなくなる
• 取り除かれていない=0、取り除かれた=1として0から(1<<M)-1までbitDP</li>
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_696/Gperm.cpp

結果

x-- 0pt 64th/241 rating 1548 -> 1523 (-25)

最終形から取り除いていくのは典型っぽいが手が出なかった。

https://togetter.com/li/1010695