Permutation [AtCoder Beginner Contest 199（Sponsored by Panasonic） E]

https://atcoder.jp/contests/abc199/tasks/abc199_e

前提知識

• bitDP

解説

https://atcoder.jp/contests/abc199/submissions/22040868

今回の問題はbitDPで解ける。
dp[msk] := 1～Nの数についてmskのものを使用していて、条件が満たされる数列の組み合わせ
なぜbitDPで考えることができるかで重要なのは以下の部分になる。

例えば3つの数を選択して数列を作っている状況を考える。

• 数列の3番目までの条件が満たされる場合は、それ以降に何をどのように足してもその満たされている条件は満たされたまま（影響しない）
• 数列の3番目までの条件が満たされる場合は、それまでの数列がどのような順番でならんでいるかは今後の選択に影響されず、何が選択されたかだけが影響する

よって、bitDPによって、条件を満たしつつどの数が使用されたかだけを保持しておけばbitDPできることになる。
あまりピンとこない場合はbitDPを学ぶことをお勧めする。

条件を満たすかの判定

bitDPの遷移時に1つ数を入れる毎に条件を確認すればいい。
check関数で確認を行う。
mskで1が立っているビット（＝選択されている数）の個数をcntとすると、この関数ではX[i]=cntのものだけ条件を確認すればいい。
それ以前のものはdpの更新的には条件が満たされていることが確約されているので確認しなくてもいいというのと、
そうしないとbitDPで使用しているmskは順番を保持しないので、最後の要素がなんであるか（これは何とかなるが、最後から2番目の要素がなんであるか）を正確に把握することができない。

int N, M;
ll dp[1 << 18];
vector<pair<int, int>> restrictions[18];
//---------------------------------------------------------------------------------------------------
int tot[19];
bool check(int msk) {
    int cnt = 0;
    rep(i, 1, N + 1) tot[i] = 0;
    rep(i, 0, N) if (msk & (1 << i)) {
        tot[i + 1]++;
        cnt++;
    }
    rep(i, 2, N + 1) tot[i] += tot[i - 1];
    
    fore(p, restrictions[cnt]) if (p.second < tot[p.first]) return false;
    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int X, Y, Z; cin >> X >> Y >> Z;
        restrictions[X].push_back({ Y, Z });
    }

    dp[0] = 1;
    rep(msk, 0, 1 << N) rep(nxt, 0, N) if (!(msk & (1 << nxt))) {
        if (check(msk + (1 << nxt))) dp[msk + (1 << nxt)] += dp[msk];
    }
    cout << dp[(1 << N) - 1] << endl;
}