C++でn人が互いに異なる帽子をかぶる組み合わせの数を求める方法

問題概要

n人の人がおり、1から40までの番号が付けられた40種類の異なる帽子があります。ここで「hats」という2次元リストが与えられ、hats[i] は i 番目の人が好む帽子の番号のリストを表します。このとき、n人全員が互いに異なる帽子をかぶるような組み合わせの総数を求めてください。答えは非常に大きな値になる可能性があるため、10^9 + 7 で割った余りを返します。

例えば、入力が [[4,6,2],[4,6]] の場合、出力は 4 になります。これは [4,6]、[6,4]、[2,4]、[2,6] の4通りの選び方が存在するためです。

解法のアプローチ

この問題は、ビットマスク動的計画法（Bitmask DP）とメモ化再帰を組み合わせることで効率的に解けます。基本的な考え方は次の通りです。

• 帽子を1つずつ順に見ていき、「その帽子をどの人に渡すか」を決める
• すでに帽子を受け取った人をビットマスクで管理する
• 全員が帽子を受け取った状態（mask == req）に到達したら1通りとしてカウントする

アルゴリズムの手順

• 剰余の値 m = 10^9 + 7 を定義する
• サイズ 55 × 2^11 の2次元配列 dp を定義する（メモ化用）
• 帽子ごとに「その帽子を好む人のリスト」を格納する2次元配列 v を定義する
• 関数 add(a, b) を定義する：((a mod m) + (b mod m)) mod m を返す
• 関数 solve(idx, mask) を定義する：
  • mask が req と等しければ 1 を返す（全員に帽子が行き渡った）
  • idx が 42 と等しければ 0 を返す（帽子を使い切った）
  • dp[idx][mask] が -1 以外ならその値を返す（メモ化による高速化）
  • ret に solve(idx + 1, mask) を加算する（この帽子を誰にも渡さない場合）
  • v[idx] 内の各 i について、mask の i ビット目が立っていなければ、ret に solve(idx + 1, mask OR 2^i) を加算する（帽子 idx を人 i に渡す場合）
  • 結果を dp[idx][mask] に保存して返す

メイン処理

• dp を -1 で初期化する
• n := x のサイズ
• v を50要素分確保する
• i = 0 から x のサイズ未満まで繰り返し、x[i] 内の各 j について v[j] の末尾に i を挿入する
• req := 2^n − 1
• ret := solve(0, 0) を呼び出して返す

C++での実装例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int m = 1e9 + 7;
int dp[55][1 << 11];
class Solution {
    public:
    vector<vector<int> > v;
    int req;
    int add(lli a, lli b){
        return ((a % m) + (b % m)) % m;
    }
    int solve(int idx, int mask){
        if (mask == req)
        return 1;
        if (idx == 42)
        return 0;
        if (dp[idx][mask] != -1) {
            return dp[idx][mask];
        }
        int ret = solve(idx + 1, mask);
        for (int i : v[idx]) {
            if (!((mask >> i) & 1)) {
                ret = add(ret, solve(idx + 1, mask | (1 << i)));
            }
        }
        return dp[idx][mask] = ret;
    }
    int numberWays(vector<vector<int>>& x){
        memset(dp, -1, sizeof dp);
        int n = x.size();
        v.resize(50);
        for (int i = 0; i < x.size(); i++) {
            for (int j : x[i]) {
                v[j].push_back(i);
            }
        }
        req = (1 << n) - 1;
        int ret = solve(0, 0);
        return ret;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{4,6,2},{4,6}};
    cout << (ob.numberWays(v));
}

入力

{{4,6,2},{4,6}}

出力

4

計算量とまとめ

帽子の数を H（最大40）、人数を n（最大10）とすると、状態数は約 H × 2^n 個であり、各状態からの遷移は最大 n 通りです。したがって時間計算量は O(H × 2^n × n)、空間計算量は O(H × 2^n) となります。n が小さいことに着目してビットマスクで「帽子をもらった人の集合」を表現し、メモ化によって同じ状態の再計算を避けるのが、この問題を現実的な時間で解くための鍵となります。