Namaran

Code daily. Without assist.

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! よりはるかに少なくなります。