ABC041

リンク

問題 http://abc041.contest.atcoder.jp/
解説 http://abc041.contest.atcoder.jp/data/abc/041/editorial.pdf

概要

A, B, C: やるだけ
D: N匹のうさぎが競争をした。ある2匹の組についてどちらのほうが早かったという情報がMこ与えられる。全体の順序としてありえるものの個数を答えよ。

D

x_iがy_iより早いという情報をグラフの有向辺と見たときに、トポロジカルソートした結果としてありえるものの個数を答える。想定解法はbit DP。
bit DPというのは集合をキーとするDPで集合をバイナリ列にエンコードするテクニックのことらしい。

「N! は大きすぎるが 2^N は小さい場合，bit DP」がよくあるらしい。

漸化式はdp[S] = sum([dp[s] for s in Sから一つだけを取り除いた集合])みたいな感じだが、制約条件を考慮にいれるとSから一つだけを取り除いた集合をすべてチェックすることにはならない。