【AtCoder】ABC187 F - Close Group

解けたのでおまけがメイン。

概要

与えられた単純無向グラフについて、辺を $0$ 本以上取り除くことでいくつかの完全グラフに分割するときの、完全グラフの個数の最小値を求めよ。

$N \leq 18$

解説

$2^ N$ 個の頂点集合を順に列挙し、それぞれの頂点集合に対し、その頂点集合に含まれる任意の $2$ 頂点間に辺があるか (入力のグラフから頂点集合を決めることで得られる誘導部分グラフが完全グラフであるか) は $O( 2^ N N^ 2 )$ で判定できる。

dp[S] = 頂点集合 S をいくつかの頂点集合に分割したときの完全グラフの個数の最小値 とする。

上記の判定問題の結果、完全グラフの場合は dp[S] = 1 で、そうでない場合はさらに頂点集合を分割しなければならない。 $1$ 頂点からなるグラフは条件を満たすので、分割していけばいずれ必ず条件を満たす。

ゆえに各集合について、下位集合から順に、全ての分割のパターンを試せば良い。

$O(2^ N )$ 個の集合の部分集合を全て列挙するためには、一見 $O(4^ N)$ かかりそうだが、以下の提出コードにあるようなビット演算を駆使することで $O(3^ N)$ でできるので、全体で $O( 2^ N N^ 2 + 3^ N )$ となり、間に合う。

提出コード

おまけその1

※以下の内容は Kiri8128, 半分にするテクを参考に、C++ 風の擬似コードや、具体例を追加したものとなっている。

ここからが本題。 $O(3^ N)$ の計算部分は以下のようなコードになる。

for (int s = 1; s < (1 << N); s++) {
    for (int t = s; t; t = (t - 1) & s) {
        dp[s] = min(dp[s], dp[s ^ t] + dp[t]);
    }
}

s が部分集合で、t は s の部分集合である。s ^ t は s から t を取り除いたものなので、これで全ての分割の場合を試せているというわけである。

ところで、以下のようなコードがある。

for (int s = 1; s < (1 << N); s++) {
    int s2 = s ^ (s & -s);
    for (int t = s2; t; t = (t - 1) & s2) {
        dp[s] = min(dp[s], dp[s ^ t] + dp[t]);
    }
}

s2 という変数が増えて、t は s2 の部分集合を列挙する形になっている。実はこれでも AC できて、実行時間がおよそ半分になる。(最も内側のループの回数が半分になる。)

s & -s というのは、Fenwick Tree の実装などでも使われるテクニックで、s の最下位ビットを取り出している。よって s ^ (s & -s) というのは、s の最下位ビットを取り除いているわけである。

例えば s = 0101 のとき s2 = 0100 、s = 1110 のとき s2 = 1100 である。

なぜ最下位ビットを取り除いた s2 に対して部分集合を列挙しても AC できるのかというと、もとのループでは s ^ t と t が一致する場合があり、同じ分割に対して二度計算を行っているためである。

例えば s = 1110 のとき t = 1110, 1100, 1010, 1000, 0110, 0100, 0010 と回るが、t = 1100 のとき s ^ t = 0010 で、これは t = 0010 に対する s ^ t = 1100 と分割の仕方が同じである。

s & -s で得られたビットが t に含まれず、常に s ^ t に含まれるようにすることで、同じ分割の仕方に対して二度計算を行わないようにしている。

これによってループ回数が半分になる。

提出コード

類題

【AtCoder】EDPC U - Grouping
- ほぼ同じ高速化手法が使えるが、そもそも $N$ が小さめではある。

おまけその2

popcount(s) = 1 となるような s に対しては、上記の改善を行うと s2 = 0 となってしまい、ループが回らなくなってしまう。ただし今回の問題についてはそのような s については dp[s] = 1 であることが保証されているため、特にバグは発生しない。(というか s はそれ以上分割できないのでループが回らないのは妥当と言える。)

おまけその3

ゼータ変換を $O(3^ N )$ で行う以下のコードがあるとする。(変換前の数列が dp で、変換後の数列が np である。)

for (int s = 0; s < (1 << N); s++) {
    for (int t = s; t; t = (t - 1) & s) {
        np[s] += dp[t];
    }
}

これを半分にするテクっぽく書き換えると以下のようになる。(先述の popcount(s) = 1 の場合分けについて気を付ける。)

for (int s = 0; s < (1 << N); s++) {
    int s2 = s ^ (s & -s);
    for (int t = s2; t; t = (t - 1) & s2) {
        np[s] += dp[t] + dp[s ^ t];
    }
}
for (int i = 0; i < N; i++) np[1 << i] += dp[1 << i];