n-knuu's logs

憧れ駆動。だいたい競プロ

SRM696 div.1 300 Gperm

寝坊したので出れなかった。

問題

50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけコストを支払う。支払うコストの合計が最小になるような順番で頂点を塗りつぶしたときのコストを求めよ。

制約

1 <= M <= 20

解法1

まず、次数0の頂点は、まず最初に塗ってしまえばよいことがわかる(あとから塗ると、その分コストが追加されるから)。
次数1以上の頂点でbitDPをすることが考えられるが、これだと2^40≒10^12となり、間に合わない。
そこで、状態として持つ頂点を減らすことを考える。
ここで、枝の両端が、次数1の頂点と次数2以上の頂点である場合、次数1の頂点から先に塗るべきであることがわかる。これは、次数2以上の頂点から先にぬると、その頂点が接続する枝のうち、少なくとも1本は2回以上のコストを払わなければならないからである。(サンプル1がいい例になっている)
ここから、次数が2以上の頂点のみを状態として持てばよいと考えられる。この場合、状態としてもつ頂点は多くても20個なので、2^20≒10^6となり、間に合う。実際は、枝の両端が次数1のみの頂点から構成されている場合も考えなければならないが、これに関しては、片方のみ状態としてもつこととすれば、状態として持つ頂点は20個以下となり、結局問題ない。

ここまで来れば、あとは dp[各頂点を塗りつぶしたかどうか] := 最小のコスト として、bitDPをすればよい。

計算量1

O(2^M M^2)
多分コストの計算を上手くやることで、O(2^M M)に落とせそう

コード1

状態として持つ頂点を上手く変換する必要があるので、実装が面倒

解法2

torusさんとかzerokugiさんの解法。
今回は「枝の両端を塗ると、コストがかかる」だが、これを「枝の片方でも塗られていなければ、コストがかからない」と考えて、どの枝の両端が塗りつぶされていないかを状態としたbitDPをする。

最初、全ての頂点を塗りつぶした状態(=全ての枝についてコストがかかる状態)から初めて、逆順に考えていく。頂点を塗りつぶされていない状態にするときに、どの枝がコストがかからなくなるかは、頂点が接続している全ての枝を調べればわかるので、以下の漸化式が成り立つ。

s: 現在塗りつぶされてない枝集合
u_i: 頂点iを塗りつぶされてない状態にしたときにコストが掛からなくなる枝集合
dp[s | u_i] = min(dp[s | u_i], dp[s] + (M-(sのビットが立っている数))

計算量2

頂点数をN(今回は50)とすると、
O(2^M N)

コード2

実装が楽。(ただしこのコードはTLEするので注意)

感想

前から順にやっていく方法だと、枝の両端の頂点の状態を持っていないとダメで、面倒だなーと思っていたが、逆順で考えれば、一つずつ考えられると分かって感動した。「全ての〜」を「少なくとも一つの〜」に言い換えるテクニックは状態数を減らすときに役立ちそう。