ABC187 F - Close Group (600)
コンテスト中の考察
点毎に辺の集合を持っておく
全ての頂点の組み合わせでその組み合わせだけをひとかたまりにできるか判定する
全ての点が全ての点に辺を持っていれば良い
その後は全ての点についてのbitDPでそれらの点について考えたときの最小数を求める
全ての$ i (1 \le i \le 2^n) で$ i \gt j となる$ dp[j] + dp[i - j] の最小値を求める
$ O(2^n)のパターンに対して$ O(2^n)の中から最小値を求めると$ O(4^n)になり間に合わない
解説の方法
それぞれのパターンについての中から最小値を求めるところを工夫すると計算量が落ちる
for (int q = p; q > 0; q = (q-1) & p) とすると、qはpの内のいくつのbitのみが立っているパターン全てを取るようになる
各bitがiだけ、iとjの両方、どちらにも含まれないの3パターンになるので$ O(3^n)となり間に合う