C++におけるビットマスキングと動的計画法（DP）の基本と実装

本記事では、まずビットマスキングと動的計画法（DP）の基本概念について学び、その後、実際の実装に関する疑問を解消できる具体例題を一緒に解いていきます。

ビットマスクとは

ビットマスク（マスクとも呼ばれます）とは、要素の集合の部分集合を符号化するためのNビットの列です。マスクの各ビットは「セット（1）」または「未セット（0）」のいずれかの状態を取り、対応する要素が部分集合に含まれているかどうかを表します。例えば、マスクのi番目のビットがセットされていれば、要素iはその部分集合に含まれていることを意味します。N個の要素を持つ集合に対しては、最大で2^N通りのマスクが存在し、それぞれが一意の部分集合に対応します。

問題を解く際には、まず初期のマスク（部分集合）に値を割り当て、そこから既に計算済みのマスクの値を利用しながら、次々と新しいマスクの値を求めていきます。このプロセスを繰り返すことで、最終的に全体の集合に対する答えを導き出すことができます。

あるマスクに対する最適な解を計算するには、含まれる要素を1つずつ取り除くすべてのパターンを試し、その結果を最終的な解に反映させていきます。

動的計画法（DP）

動的計画法とは、部分問題を解いてその結果を保存しておくことで、重複する他の部分問題の計算に再利用できるようにする最適化手法です。

それでは、ビットマスキングと動的計画法を組み合わせて解く具体的な問題を見ていきましょう。

問題

1から50までの番号が付けられた50個の帽子があります。N人はそれぞれいくつかの帽子を所持しています。ある日、全員が帽子をかぶってパーティーに参加することになりましたが、誰もが個性的に見えるよう、全員が異なる番号の帽子をかぶることに決めました。人数nと、各人が所持している帽子の番号のリストが与えられたとき、全員がユニークな帽子をかぶれる組み合わせの総数を求めてください。

入力の1行目には人数nが、続くn行には各人の帽子のコレクションが与えられます。

入力例：

3
4 45 10
25
45 10

出力例：

4

解説：

考えられるすべての組み合わせは、(4, 25, 45)、(4, 25, 10)、(45, 25, 10)、(10, 25, 45) の4通りです。

組み合わせの数は非常に大きな値になる可能性があるため、答えは1000000007で割った余りとして出力します。

この問題に対する単純な解法は、帽子をかぶる人のすべての組み合わせを列挙することです。最初の集合から順に処理し、残りの集合を再帰的に調べていきます。しかし、この方法は計算量が膨大になり、非効率です。

より効率的なのが、ビットマスキングとDPを組み合わせた解法です。例えば10人の場合、サイズ2¹⁰のマスクを作成し、さらに51個分の帽子情報を格納するベクトルを用意します。そして、これらを活用して再帰的に解を求めていきます。

実装例

上記の解法を実装したプログラム：

#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
    if (mask == allmask) return 1;
    if (i > 100) return 0;
    if (dp[mask][i] != -1) return dp[mask][i];
    long long int ways = uniqueCaps(mask, i+1);
    int size = caps[i].size();
    for (int j = 0; j < size; j++) {
       if (mask & (1 << caps[i][j])) continue;
           else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
           ways %= (1000000007);
    }
    return dp[mask][i] = ways;
}
int main() {
    int n = 3;
    // 人物1のコレクション
    caps[4].push_back(0);
    caps[45].push_back(0);
    caps[10].push_back(0);
    // 人物2のコレクション
    caps[25].push_back(1);
    // 人物3のコレクション
    caps[45].push_back(2);
    caps[10].push_back(2);
    allmask = (1 << n) - 1;
    memset(dp, -1, sizeof dp);
    cout<<"パーティーで全員がユニークな帽子をかぶる方法の数：	"<<uniqueCaps(0, 1);
    return 0;
}

出力

パーティーで全員がユニークな帽子をかぶる方法の数：4