ICPC 2017 国内予選D: 弁当作り

問題の解説はせずに、グレイコードの紹介をする。

iに対してi^i>>1を計算して列挙すると、隣接する値のハミング距離が 1 になる。これをグレイコードと呼ぶ。

0000 => 0000
0001 => 0001
0010 => 0011
0011 => 0010
0100 => 0110
0101 => 0111
0110 => 0101
0111 => 0100
1000 => 1100
1001 => 1101
1010 => 1111
1011 => 1110
1100 => 1010
1101 => 1011
1110 => 1001
1111 => 1000

この性質はn<mのときの全列挙に使える。前回のループの値から1ビットしかずれていないため更新が容易に行える。

#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>

int ctz(int n) {
    int ret = 0;
    while (~n & 1) {
        ret++;
        n >>= 1;
    }
    return ret;
}

int bitcnt(int n) {
    int ret = 0;
    while (n > 0) {
        ret++;
        n &= n - 1;
    }
    return ret;
}

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<std::string> b(n);
    std::vector<std::bitset<500>> bs(n);
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
        for (int j = 0; j < m; j++) {
            bs[i][j] = b[i][j] == '1';
        }
    }

    int ans = 0;
    std::bitset<500> sum;
    for (int i = 1; i < 1 << n; i++) {
        int x = i ^ i >> 1;
        sum ^= bs[ctz(i)];
        if (sum.none()) {
            ans = std::max(ans, bitcnt(x));
        }
    }

    std::cout << ans << std::endl;
}

この実装ではグレイコード小手先テクニックが使われている。iに対応するグレイコードをf(i)と表したとき、f(i-1)^f(i)=i&-iになっている。原理を理解するには、i^i-1がどうなるかを確認し、f(i)^f(i-1)=i^(i>>1)^(i-1)^(i-1>>1)がどうなるのかを調べると良い。

f(i-1)^f(i)=i&-iなので、以下のような方法でもグレイコードは列挙できる。

#include <iostream>
#include <bitset>

int main() {
    int x = 0;
    for (int i = 0; i < 1 << 4; i++) {
        x ^= i & -i;
        std::cout << std::bitset<4>(x) << std::endl;
    }
}

部分集合列挙に関しては以下のような感じ(原理は同様)。i^i>>1のような直接的な方法があるかは不明。

int main() {
    const int sup = 0b10010101;
    int x = 0;
    for (int jj = sup; jj != 0; jj = (jj - 1) & sup) {
        x ^= jj & -jj;
        std::cout << std::bitset<8>(x) << std::endl;
    }
}

更新履歴