twXIIve #C++

twXIIve

解法

難しいのでステップを踏んで解いてく。

1. bitDPしたい気持ちになる

問題を読むとN!したい気持ちになる。
制約の最大が$N=12$で小さい
N!したい気持ちになってNの制約が小さい時はbitDPできるって強い人が言ってたのでできる
dp[i]: iのビットが立ってる人を使用した時の組み合わせの数って感じで定義してみる。
dp[これから使う人 | すでに使った人] += dp[すでに使った人]って感じでできそう

2. 何も考えずに列挙する

何も考えずに列挙すると以下のようになる。
赤字はすでに使ったビット。黒字はこれから使うビット。

3. これから使うビットがunusedの部分集合出ない場合を除く

さっきの表ではおかしな集合の集合が列挙されてた。(1)(1)とか(1, 3)(3)とか。
これはこれから使うビットがunusedの部分集合になってないから。なのでその判定を入れる。すると以下の表のようになる。

4. 重複の数え上げを防ぐ

ただ、列挙したグループに重複が発生している
重複してるのは、(1)(2)と(2)(1)、(1)(3)と(3)(1)、(2)(3)と(3)(2)、(1, 2)(3)と(3)(1, 2)。
ビットの数値で表現すると(1)(2)と(2)(1)、(1)(4)と(4)(1)、(2)(4)と(4)(2)、(3)(4)と(4)(3)になる。これを見ると、$すでに決まっているグループのbit < 新しいグループのbit$になってるもののみを列挙すればいい感じがする。
ソースコードでいうと以下のような感じのイメージ

// 重複ありの数え方
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // i, jのペア
  }
}

// 重複なしの数え方
for (int i = 0; i < n; i++) {
  for (int j = i+1; j < n; j++) {
    // i, jのペア
  }
}

すると表は以下のようになり、集合の列挙がうまくできてることがわかる

5. その他

ここまでで大体の処理はわかった
あとは重複を防いだりするだけ

O(4^NM)の解法コード

$4^{12} \times \frac{12*(12-1)}{2}=1107296256$で大体$10^9$ステップ回す。ギリギリっぽいけどなんか普通に通る。すごいね

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

#define int long long

int N, M;
vector<int> u, v;
int dp[1<<12]; // dp[i]: iの立っているビットの人を使用したときの組み合わせの数

void solve() {
  dp[0] = 1;
  for (int used = 0; used < (1 << N); used++) { // 使用済みのbitを列挙するループ
    int unused = used ^ ((1 << N) - 1);  // usedで使わなかったbit
    for (int use = used+1; use <= unused; use++) { // これから使用するbitを列挙するループ
      // useがunusedの部分集合になってるかの判定
      if ((use & unused) != use) {
        continue;
      }

      // 同じグループになっていいものが含まれるかの判定
      bool ok = true;
      for (int i = 0; i < M; i++) {
        if (((use >> u[i]) & 1) and ((use >> v[i]) & 1)) {
          ok = false; break;
        }
      }

      // dp[新しいグループのbit | すでに決まっているグループのbit] += dp[すでに決まっているグループのbit]
      if (ok) {
        dp[use | used] += dp[used];
      }
    }
  }

  cout << dp[(1 << N) - 1] << endl;
}

signed main() {
  cin >> N >> M;
  u.resize(M);
  v.resize(M);
  for (int i = 0; i < M; i++) {
    cin >> u[i] >> v[i];
    u[i]--, v[i]--;
  }

  solve();

  return 0;
}

O(3^N M)の解法コード

$3^{12} \times \frac{12*(12-1)}{2}=6377292$。大体$10^6$ステップくらい。なので余裕で間に合う。
部分集合列挙の部分を$O(4^N)$から$O(3^N)$にした。なんでこのコードでうまく動くかはよくわからない。なんか動く。

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

#define int long long

int N, M;
vector<int> u, v;
int dp[1<<12];

void solve() {
  dp[0] = 1;
  for (int used = 0; used < (1 << N); used++) {
    int unused = used ^ ((1 << N) - 1);
    for (int use = unused; use > 0; use=(use-1)&unused) { // これでunusedの部分集合を全列挙できる
      // useがunusedの部分集合かを判定する必要がなくなる
      // if ((use & unused) != use) {
      //   continue;
      // }
      if (!(used < use)) continue; // used < useになるのやつだけ列挙する

      bool ok = true;
      for (int i = 0; i < M; i++) {
        if (((use >> u[i]) & 1) and ((use >> v[i]) & 1)) {
          ok = false; break;
        }
      }

      if (ok) {
        dp[use | used] += dp[used];
      }
    }
  }

  cout << dp[(1 << N) - 1] << endl;
}

signed main() {
  cin >> N >> M;
  u.resize(M);
  v.resize(M);
  for (int i = 0; i < M; i++) {
    cin >> u[i] >> v[i];
    u[i]--, v[i]--;
  }

  solve();

  return 0;
}

メモ

ビット列による部分集合表現【ビット演算テクニック Advent Calendar 2016 1日目】。ビットの気持ちがわかる。{A, B, C} = 111で{A, C} = 101の部分とか
ビットによる部分集合の列挙
bitによる部分集合の列挙と数学的理解。証明とか書いてある
駆引取引。この問題が類題っぽい。つたさんに過去聞いてた（ツイッターで聞いたやつ）。へくとさんにも聞いたやつ
部門分け。これも類題っぽい？
Grouping。これはEDPCの類題。典型問題だったみたい
アリ本144ページにビットの気持ちみたいなのが載ってる

感想

アホみたいにむずい。
「使用済み」から「使用済み | 未使用」への遷移でDPできるって気づくフェーズも難しい。どうやって気づくんだこれ
完全に理解した感がないので解き直したい