D - 徒競走 AtCoder Beginner Contest 041

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

問題概略　

N匹のうさぎがいる。xi < yi がM通り与えられる。

とりうる組み合わせをもとめろ

制約

• 2≦N≦16
• 1≦M≦N(N−1)⁄2
• 1≦x_i，y_i≦N
• x_i≠y_i
• (x_i，y_i) の組はすべて相異なる。
• すべての観客の情報に合致するような着順が少なくともひとつ存在する。

解法

N!が間に合えば解ける。間に合わないのでbitDP。

bitDPといえばすでに試した物を固定したい。

したとして、どうやって追加するか悩む。

ここで、bitDPはある状態への埋め方が全パターン探索されることを思い出そう。

111なら 110,101,011　の全パターンから遷移される。

つまり新しく追加する物が、右端におけるかということを調べる場合、全てのSに含まれる要素についてその判定が行われる。

よって、dp[s] を状態sの組み合わせ全て。

dp[s + i] を状態sにiを右端に加えられる時dp[s]追加するという風にすればdp[s]は完成される。

問題の芯

bitDPは全通り試される。

static int N, M;
    static boolean[][] edge;
    static long[] dp;// stateで作れる組み合わせ 集める

    public static void main(String[] args)
    {
        N = sc.nextInt();
        M = sc.nextInt();
        edge = new boolean[N][N];
        dp = new long[1 << N];
        for (int i = 0; i < M; i++)
        {
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            edge[x][y] = true;
        }
        dp[0] = 1;
        for (int s = 0; s < (1 << N); s++)
        {
            for (int r = 0; r < N; r++)
            {
                if (((s >> r) & 1) == 1) continue;//すでにrがあったら無視
                boolean isOk = true;
                for (int l = 0; l < N; l++)
                {
                    if (((s >> l) & 1) == 0) continue;//lが含まれていなかったら無視
                    if (edge[r][l]) isOk = false;
                }
                if (isOk) dp[s | 1 << r] += dp[s];
            }
        }
        System.out.println(dp[(1 << N) - 1]);


    }