けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 187 F - Close Group (青色, 600 点)

 O(3^{N}) な bit DP としてよく知られている問題ですね!

EDPC U - Grouping の類題と言える!

atcoder.jp

問題概要

頂点数  N、辺数  M の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラフがいずれもクリークとなるようにしたい。

分割されたグループの個数の最小値を求めよ。

制約

  •  1 \le N \le 18

解法 (1): O(3^{N}) の bit DP

こんな bit DP をすれば OK!!!

  • dp[bit] ← bit に対応する頂点集合をいくつかのクリークに分割するとき、分割されたクリークの個数の最小値

そして遷移は次の通り。

// 頂点集合 add が、bit と共通要素を持たず、クリークであるとする
chmin(dp[bit | add], dp[bit] + 1);

これは一見すると、bit が  2^{N} 通りあって、そのそれぞれに対して add が  O(2^{N}) 通りあって、全体で  O(4^{N}) 通りに思えてしまうかもしれない。しかし実はちゃんと解析すると  O(3^{N}) となって十分間に合うのだ。具体的には

add は、bit の補集合の部分集合しか動かない

という点に着目する。実装上はこんな感じにできる。ここで、「部分集合の部分集合を列挙する方法」を活用している。

for (int bit = 0; bit < (1<<N); ++bit) {
    int cbit = (1<<N) - 1 - bit; // 補集合
    for (int add = cbit; ; add = (add-1) & cbit) {
        if (!add) break;

        // 頂点集合 add がクリークかどうかを表す配列 ok を予め求めておく
        if (ok[add]) chmin(dp[bit|add], dp[bit] + 1);
    }
}

この処理の計算量が  O(3^{N}) であることを示そう。実は簡単だ。(bit, add) のとりうる値は次のように考えると  3^{N} 通りしかない。各頂点  i = 0, 1, \dots, N-1 について、

  • 頂点  i は頂点集合 bit に含まれる
  • 頂点  i は頂点集合 bit に含まれないが、頂点集合 add に含まれる
  • 頂点  i は頂点集合 bit, add のいずれにも含まれない

という 3 パターンしかない。したがって、考えられる状況は  3^{N} 通りなのだ。以上から、今回の bit DP の計算量が  O(3^{N}) であることがわかった。

コード

前処理として、以下の配列を求めている。

  • ok[bit] ← 頂点集合 bit がクリークかどうか
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N, vector<int>(N, false));
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = true;
    }

    vector<bool> ok(1<<N, true);
    for (int bit = 0; bit < (1<<N); ++bit) {
        vector<int> vs;
        for (int i = 0; i < N; ++i) if (bit & (1<<i)) vs.push_back(i);
        for (int i = 0; i < vs.size() && ok[bit]; ++i) {
            for (int j = i+1; j < vs.size() && ok[bit]; ++j) {
                if (!G[vs[i]][vs[j]]) ok[bit] = false;
            }
        }
    }

    const int INF = 1<<29;
    vector<int> dp(1<<N, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        if (dp[bit] >= INF) continue;
        int cbit = (1<<N) - 1 - bit;
        for (int add = cbit; ; add = (add-1) & cbit) {
            if (!add) break;
            if (ok[add]) chmin(dp[bit|add], dp[bit] + 1);
        }
    }
    cout << dp[(1<<N)-1] << endl;
}

解法 (2):補グラフの彩色数

クリークといえば、補グラフをとれば「安定集合」になる。安定集合とは、

「頂点集合の部分集合であって、どの 2 頂点間にも辺がないようなもの」

のことを指す。クリークを見たら補グラフをとるのはありかもしれない。さて、もとのグラフで同一のグループの頂点は同じ色で塗り、異なるグループの頂点は異なる色で塗るとしたとき、

  • もとのグラフで条件を満たしている場合、同じ色の頂点間にはすべて辺があるので、補グラフでは辺彩色 (同じ色の頂点間には辺がない) になっている
  • 補グラフで辺彩色になっている場合、同じ色の頂点間にはすべて辺がないので、もとのグラフでは同じ色の頂点間にはすべて辺がある

というふうになっている。つまり、補グラフの彩色数を求めれば OK。補グラフの彩色数は次の記事で書いた。計算量は  O(N2^{N}) でできる!

drken1215.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;

// 彩色数
long long modpow(long long a, long long n, long long MOD) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
int chromatic_number(const vector<vector<int> > &G) {
    const int MOD = 1000000007;
    int n = (int)G.size();
    vector<int> neighbor(n, 0);
    for (int i = 0; i < n; ++i) {
        int S = (1<<i);
        for (int j = 0; j < n; ++j)
            if (G[i][j])
                S |= (1<<j);
        neighbor[i] = S;
    }
    
    // I[S] := #. of inndepndet subset of S
    vector<int> I(1<<n);
    I[0] = 1;
    for (int S = 1; S < (1<<n); ++S) {
        int v = __builtin_ctz(S);
        I[S] = I[S & ~(1<<v)] + I[S & ~neighbor[v]];
    }
    int low = 0, high = n;
    while (high - low > 1) {
        int mid = (low + high) >> 1;
        
        // g[S] := #. of "k independent sets" which cover S just
        // f[S] := #. of "k independent sets" which consist of subseta of S
        // then
        //   f[S] = sum_{T in S} g(T)
        //   g[S] = sum_{T in S} (-1)^(|S|-|T|)f[T]
        long long g = 0;
        for (int S = 0; S < (1<<n); ++S) {
            if ((n - __builtin_popcount(S)) & 1) g -= modpow(I[S], mid, MOD);
            else g += modpow(I[S], mid, MOD);
            g = (g % MOD + MOD) % MOD;
        }
        if (g != 0) high = mid;
        else low = mid;
    }
    return high;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> G(N, vector<int>(N, 1));
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = 0;
    }
    cout << chromatic_number(G) << endl;
}