【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]); }