2026-09-02
walk.cpp
#include <cstdio>
#include <set>
#include <utility>
std::set<std::pair<unsigned, int>> states;
void walk(unsigned visited, int at, int n) {
states.insert({visited, at});
for (int next = 0; next < n; ++next)
if (!(visited >> next & 1))
walk(visited | 1u << next, next, n);
}
int main() {
walk(1u, 0, 4);
std::printf("%zu\n", states.size());
}
これは何を出力するでしょうか?
Answer
13 です。
walk は頂点0から出発し、まだ訪れていない頂点へ移る道順をすべてたどります。訪れた頂点の集合は visited のビットで表し、頂点 k を訪れていればビット k が1です。4頂点のどこからどこへでも移れるので、訪れた頂点の数が1、2、3、4の道順はそれぞれ1通り、3通り、3 × 2 = 6通り、6通りで、walk は合わせて16回呼ばれます。
ただし states は std::set なので、同じ組 {visited, at} を2回入れても要素は増えません。ここで、ビットで表した集合は訪れた順番を持たないことが効いてきます。0→1→2 と 0→2→1 は今いる頂点が違うので別の組ですが、4頂点すべてを訪れた6通りの道順は、最後にいる頂点が1、2、3のどれかなので、組は3つしかありません。重なった3回は要素を増やさないので、16 − 3 = 13 です。std::set に気付いても、道順が違えば組も違うと考えると、16 と答えることになります。
訪れた頂点の集合と今いる頂点が同じなら、その先の進み方も同じです。そこで、道順ではなくこの組を状態として計算を進める方法をビットDP(bit DP)と呼びます。頂点が n 個なら状態は多くても 2n × n 個で、道順の数 n! よりはるかに少なくなります。