ABC041 D - 徒競走

問題

問題概要

M個のクエリ満たす数字の並びを求める問題。

解法

まず、　どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計算していく。
現在見ている集合の中で場合の数を考えれば、集合の要素にないものを考える必要はない。言い換えると、その集合内でどのような順番でその数字を並べたとしても（ただし条件を満たす形で）、そのあとの数字の並べ方の場合の数は変わらない。だから、並べる数字の集合のみを考えて、dpすればいい。p47がわかりやすい。参考サイト
dpの表ぽいのを書いてみた。dp表
[追記]このサイトの解説がわかりやすい参考サイト

ミス

bitDPであることは制約からすぐわかった。ただ与えられる情報から制限されてしまう部分をどのようにやればいいかわからなかった。情報をすべて満たす集合をあらかじめ計算しておけばいい。 TLE30点解法(全探索しているだけ)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int main(void){
    int n, m;
    cin >> n >> m;
    vpint inf;
    rep(i, m){
        int x, y; scanf("%d %d", &x, &y);
        x--; y--;
        inf.push_back(mp(x, y));
    }
    ll ans = 0;
    vint data(n);
    rep(i, n) data[i] = i;//昇順に入れる
    do{
        int nowx, nowy;
        bool flagfi, flagse;
        rep(i, m){//infをみる
            flagfi = false; flagse = false;
            rep(j, n){//ウサギの順番を探す
                if(inf[i].fi == data[j]){
                    nowx = j;
                    flagfi = true;
                }
                if(inf[i].se == data[j]){
                    nowy = j;
                    flagse = true;
                }
                if(flagfi == true && flagse == true) break;
            }
            if(nowx > nowy) break;
            if(i == m - 1){
                ans++;
            }
        }
    }while(next_permutation(data.begin(), data.end()));
    printf("%lld\n", ans);
    return 0;
}

コード

満点解法

#include <iostream>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <cstdio>
using namespace std;
#define mp make_pair
#define fi first
#define se second  
#define rep(i,n) for(int i=0;i<(n);i++)
 
int n, m;
bool flag[(1 << 16)];//flagの桁数めのbitが立っている時(1)
long long dp[(1 << 16)];

//&演算子を用いて、現在見ているmaskに対して、position桁目が1かどうかを見ている
/*
mask = 01101(2進数)　position=2の時
mask            0 1 1 0 1
(1 << position) 0 0 1 0 0
mask & (1 << position) = 00100となり、positionの位置にbitが立っているかがわかる。
立っていなければ演算結果が0となる
*/
bool contain(int mask, int position){
    if((mask & (1 << position)) != 0) return true;
    else return false;
}
 
int main(void){
    scanf("%d %d", &n, &m);
    vector<pair<int, int> > inf;
    rep(i, m){
        int x, y; scanf("%d %d", &x, &y);
        x--; y--;//0オリジン
        inf.push_back(mp(x, y));
    }
 
    //与えられた情報に矛盾しない集合を探す
    for(int mask = 0; mask < (1 << n); ++mask){
        flag[mask] = true;//初期化
        rep(i, m){//与えられた情報をすべて確認
            //集合が矛盾している
            if(contain(mask, inf[i].se) == true && contain(mask, inf[i].fi) == false){
                flag[mask] = false;
            }
        }
    }
 
    dp[0] = 1;//空集合の時は0! = 0で場合の数は0通り
    for (int mask = 1; mask < (1 << n); ++mask){
        //集合が与えられた条件を見たしている時
        if(flag[mask] == true){
            rep(i, n){
                //集合が条件を満たすもので、maskのiビット目が1である時
                /*
               mask ^ (1 << i)でmaskのiビット目のみを0にできる（maskのiビット目が1である時）
               */
                if(contain(mask, i) == true && flag[mask ^ (1 << i)] == true){
                    //maskのibit目を0にしたものの場合の数を足す(だだし条件を満たしていれば)
                    dp[mask] += dp[mask ^ (1 << i)];
                }
            }
        }
    }
    printf("%lld\n", dp[(1 << n) - 1]);
    return 0;
}