twXIIve

- [twXIIve](https://www.hackerrank.com/contests/bbc001/challenges/bbc001-d/problem)

## 解法

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

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

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

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

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

<img width="1087" alt="twXIIve.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/6f9549f5-ca43-ab9a-85c6-2940dc91563e.png">



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

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

<img width="1087" alt="twXIIve2.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/da3d3ce0-28cd-b9a1-fcd0-b7136ed69f16.png">


### 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$になってるもののみを列挙すればいい感じがする。
- ソースコードでいうと以下のような感じのイメージ

```cpp
// 重複ありの数え方
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のペア
  }
}
```

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

<img width="1087" alt="twXIIve3.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/edace783-a82f-4d83-e699-bfa07ff2adb9.png">



### 5. その他

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



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

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

```cpp
#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)$にした。なんでこのコードでうまく動くかはよくわからない。なんか動く。

```cpp
#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日目】](https://primenumber.hatenadiary.jp/entry/2016/12/01/000000)。ビットの気持ちがわかる。{A, B, C} = 111で{A, C} = 101の部分とか
- [ビットによる部分集合の列挙](https://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966)
- [bitによる部分集合の列挙 と 数学的理解](https://ark4rk.hatenablog.com/entry/2018/03/07/230257)。証明とか書いてある
- [駆引取引](https://atcoder.jp/contests/yahoo-procon2018-qual/tasks/yahoo_procon2018_qual_c)。この問題が類題っぽい。つたさんに過去聞いてた（[ツイッターで聞いたやつ](https://twitter.com/nomikura/status/962326437431685120)）。へくとさんにも聞いたやつ
- [部門分け](https://atcoder.jp/contests/arc056/tasks/arc056_c)。これも類題っぽい？
- [Grouping](https://atcoder.jp/contests/dp/tasks/dp_u)。これはEDPCの類題。典型問題だったみたい
- アリ本144ページにビットの気持ちみたいなのが載ってる



## 感想

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