ABC041-D:徒競走

問題

https://beta.atcoder.jp/contests/abc041/tasks/abc041_d

N 頂点上のグラフに、M本の有向辺が与えられる。M本の有向辺の条件を満たし、N 個の頂点を左から右へ横一列に並べる並べ方は何通りか。

制約

• 2 <= N <= 16
  
• 1 <= M <= N(N-1)/2
  

考え方

トポロジカルソートの数え上げ問題である。頂点集合を S としてDAG上の右から順序を確定していくこととする。

サンプル1を例に考える。 S = {1, 2, 3} である。 頂点集合 S をトポロジカルソートする並べ方を f(S) を表すこととする。空集合をトポロジカルソートする方法の通り数は f(φ) = 1 とする。S をトポロジカルソートをするとき、Sの中で一番右になれる頂点は {1, 3} のいずれかである。よって、

f({1, 2, 3}) = f({2, 3}) + f({1, 2})
= f({2}) + f({2})
= f(φ) + f(φ)
= 1 + 1 = 2

となる。
f({2, 3}) は 頂点 1 が一番右においた場合、 f({1, 2}) は頂点 3 を一番右においた場合である。頂点集合 S の中でトポロジカルソートしたときに一番右になることのできる頂点 i の条件は、 j ∈ S なる他の頂点 j について i から j への有向辺がないことである。この計算量は O(N² 2^N) である。事前に各頂点に対して有向辺が存在する頂点を計算しておくと、ビットの論理積をとることでで判定することができるので O(N 2^N) になる。

       int n, m;
        long[] s = new long[1<<n];
        boolean[][] mat;
        long[] memo;
        public void solve(int testNumber, InputReader in, PrintWriter out) {

            n = in.nextInt();
            m = in.nextInt();
            mat = new boolean[n][n];
            memo = new long[1<<n];
            Arrays.fill(memo, -1);

            for (int i = 0; i < m; i++) {
                int x = in.nextInt()-1, y = in.nextInt()-1;
                mat[x][y] = true;
            }

            long ans = rec((1<<n) - 1);
            out.println(ans);
        }

        long rec(int state) {

            if (memo[state] != -1) {
                return memo[state];
            }

            if (Integer.bitCount(state) == 0) {
                return 1;
            }

            long ret = 0;

            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 1) {
                    boolean ok = true;
                    for (int j = 0; j < n; j++) {

                        if (i == j) continue;
                        if (((state >> j) & 1) == 1) {
                            if (mat[i][j]) {
                                ok = false;
                            }
                        }
                    }

                    if (ok) {
                        ret += rec(state - (1<<i));
                    }
                }
            }
            return memo[state] = ret;
        }

ポイント

bitDPによってナイーブ解が O(N!) になる問題を O(N * 2^N) 程度に落とせる。状態を集合として取ることで、順序関係を気にしなくて良くなるため計算量が落ちるため。加えて、頂点集合 2^N に対して、各ビットを全探索することが多いイメージである。