静かで孤独な日記

のんびりたまに

ABC041-D 徒競走

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,m,h,w;
ll dp[(1<<20)];
vector<int> v[20];

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;x--;y--;
        v[y].push_back(x);
    }
    dp[0]=1;
    for(int i=0;i<(1<<(n+1));i++){
        if(dp[i]==0)continue;
        for(int bit=0;bit<n;bit++){
            if(i&(1<<bit))continue;
            else{
                bool flag=1;
                for(int j=0;j<(int)v[bit].size();j++){
                    if(i&(1<<v[bit][j]))continue;
                    else flag=0;
                }
                if(flag)dp[i|(1<<bit)]+=dp[i];
            }
        }
    }
    cout<<dp[(1<<n)-1]<<endl;
    return 0;
}
  • どうやってやるのかなーって考えてる時に bitdpするっていう選択肢を考えなかったのが辛い。
  • 一瞬解説をみて bitdpだとわかったので、それからは自分で考えてやった。
  • k- bit目が0なら k+1番のウサギはまだゴールしてない、1ならゴールしてると考えてやる。
  • 先にゴールしていてほしいウサギが全部ゴールしているなら、着目しているウサギもゴールさせて良い。
  • そんな感じで最後は全員ゴールした状態の通り数なので、全ての bitが1のdp配列を見れば良い。
  • 制約に16があったら bitdpを疑おうね自分!!!!