ABC041D

abc041.contest.atcoder.jp

解説を読んでも満点解法がなかなかわからず苦労したのでそのメモです。

　まずトポロジカルソートは有向辺が全て1方向へ向くようにソートをソートをすることです。入力例1についてトポロジカルソートを行ってみると以下の2通りになります。

このトポロジカルソートの種類を求める問題と考えることができます。
　解説のように漸化式を計算することでなぜトポロジカルソートができるか考えます。頂点vをもっとも右に置くことができれば、頂点vを除いた部分集合について同じことを再帰的に行うことでトポロジカルソートとなります。部分集合Sの中でもっとも右における頂点vとは vからS-{v} への有向辺がないことと同義です。その部分集合の他の頂点に対する有向辺があると左向きの有向辺が生じてしまうためトポロジカルソートの条件を満たせないということです。
　このような集合を含んでいる漸化式を扱うときにはBitDPがよくある手段（らしい）です。

頂点 1 2 3 4
　　 0 0 1 0  S = {3}
　　 1 1 0 1  S = {1, 2, 4}

といったようにビットが1の部分の頂点を含んでいる部分集合と対応させることで集合を表現します。0から2^Nまで小さい方から順に計算していくことで答えを求めることができます。これをコードで実装します。

以下蛇足。bit演算に慣れていなかったこともあってBitDPの実装に時間をかけてしまった。集合を扱うときは鉄板の方法っぽい。あとN<=16とかでO(N!)だと間に合わないけどO(2^N)だと間に合うときはBitDPを使う方法のことが多いらしい。Nの制約から使うアルゴリズムが想像つくようになってきた。