2026-09-02
count_orders.cpp
#include <utility>
#include <vector>
long long count_orders(int n, const std::vector<std::pair<int, int>>& rules) {
}
0 から n - 1 までの番号が付いた n 個の作業を、1つずつ順に行います。rules の要素 {a, b} は、作業 a を作業 b より前に行うという条件です。すべての条件を満たす作業の順番が何通りあるかを返す count_orders を書いてください。条件を満たす順番がなければ0を返します。n は1以上20以下です。
入力例 1
count_orders(4, {})
出力例 1
24
入力例 2
count_orders(4, {{0, 1}, {0, 2}, {2, 3}})
出力例 2
3
入力例 3
count_orders(2, {{0, 1}, {1, 0}})
出力例 3
0
Reference
long long count_orders(int n, const std::vector<std::pair<int, int>>& rules) {
std::vector<unsigned> need(n);
for (auto [a, b] : rules)
need[b] |= 1u << a;
std::vector<long long> ways(1u << n);
ways[0] = 1;
for (unsigned done = 0; done < ways.size(); ++done)
for (int t = 0; t < n; ++t)
if (!(done >> t & 1) && (need[t] & ~done) == 0)
ways[done | 1u << t] += ways[done];
return ways.back();
}
入力例1のように条件がなければ、答えは4個の順列(permutation)の数 4! = 24 です。n が20だと 20! は約2.4 × 1018 通りあり、順番を1つずつ試すのは間に合いません。そこで、終えた作業の並び順は捨てて、どの作業を終えたかの集合だけを覚えます。次にどの作業を行えるかは、終えた作業の集合だけで決まるからです。集合 done はビットで表し、ways[done] に、done の作業をちょうど終えるまでの順番の数を入れます。状態は 220、約100万個です。
作業 t を次に行えるのは、t がまだ終わっておらず、t より前に行うべき作業の集合 need[t] がすべて done に入っているときです。need[t] & ~done は、前に行うべきなのにまだ終えていない作業の集合です。done | 1u << t は done より大きい数なので、done を小さい順に処理すれば、ways[done] を使う時点でその値はもう増えません。入力例3のように条件が循環していると、どちらの作業も最初に行えず、全体の集合に一度も数が足されないので0が返ります。
条件を満たす順番は、グラフの用語でトポロジカル順序(topological order)と呼ばれます。掲載したのは参考実装で、唯一の正解ではありません。done から1ビットずつ取り除く向きに、メモ化した再帰で数えても同じ答えになります。