【ABC041】D - 徒競走

問題概要

匹のうさぎがいる. 人の観客から, うさぎがうさぎよりも先にゴールしたという情報を得た. これら全ての情報に合致する着順が何通りあるかを求めよ.

制約

• 
• 

考察

bitDPをする. dp[何匹見たか][状態]としたとき, 各うさぎがすでにゴールしたかをbitの状態として持つ(bitが立っていればすでにゴールしているとする).

遷移

dp[n][stat]からの遷移を考える. 次に遷移する候補は, statのbitが立っていないものから選ぶ.

候補のうさぎをとすると, 情報と照らし合わせたとき

• なら, はまだゴールしていないはず.
• なら, はすでにゴールしているはず.

この2つの条件を満たしていないと, 情報に合致していないと分かり, 遷移を行わない.

満たしているときは, dp[n+1][stat+(1<<p)] += dp[n][stat]として配っていけば良い.

よって遷移にかかって, 全体の計算量は, .

ただ, 現状この計算量だと最悪でを超えてしまうので, 遷移する際に無駄な情報を見ない(うさぎに関する情報だけを集約する)ようにしてごまかした().

ACコード(C++🔆)

ll dp[22][77777];
vl after[22], before[22];

signed main() {

  SS(ll, N, M);
  REP(i, M) {
    SS(ll, x, y);
    --x, --y;
     after[x].PB(y);
    before[y].PB(x);
  }

  dp[0][0] = 1;

  REP(n, N) {
    REP(stat, (1LL << N)) {
      // まだゴールしてないなら, dp[n][stat]からdp[n+1][stat+(1<<i)]に遷移できるか確認
      REP(i, N) if ((stat & (1LL << i)) == 0) {
        bool canTransit = true;
        EACH(aft,  after[i]) if ((stat & (1LL << aft)) != 0) canTransit = false;
        EACH(bef, before[i]) if ((stat & (1LL << bef)) == 0) canTransit = false;
        if (!canTransit) continue;
        dp[n + 1][stat + (1LL << i)] += dp[n][stat];
      }
    }
  }
  
  print(dp[N][(1LL << N) - 1]);

}