2020年3月30日月曜日

ARC 049 C - ぬりまーす

ARC 049 C - ぬりまーす

タイプ2の条件はひとまず無視して考える。

タイプ1のそれぞれの条件(x,y)(x, y)についてyyからxxに辺を張ったグラフGGを与えたとき、問われていることは「GGから入次数が00の頂点を次々に消していくとき、最大で何個消せるか?」ということだった。この個数に消す順序は関係ないので、実際に自由に消していって確かめればよい。具体的には、入次数が00の頂点をすべてキュー(あるいはスタック)に入れてBFS(あるいはDFS)をすればO(N+A){\mathcal O}(N+A)でできる。手順としては、キューから頂点を取り出したら、隣接頂点の入次数を1ずつ下げて、入次数が00になったものをキューに入れればよい。あるいは、この制約ならBellman-Fordっぽく入次数が0の頂点の隣接頂点の入次数を下げる操作をNN周繰り返す、でもよさそう。(O(NA){\mathcal O}(NA))

タイプ2の条件(u,v)(u, v)については、

  1. uuを選ばないとする(=頂点uuは存在しないものとする)
  2. vvを選ぶ場合にはuuを先に選んでいなくてはならないとする。

の2通りを調べれば十分で、後者はタイプ1と同じなので上の問題に帰着できている。タイプ2の条件は十分に少ないので、2B2^B通りのグラフを調べればよい。O((N+A)2B){\mathcal O}((N+A)2^B)