AtCoder Educational DP Contest U問題解いてみた

今回の問題

問題文

$N$ 羽のうさぎたちがいます。 うさぎたちには $1, 2, \ldots, N$ と番号が振られています。
各 $i, j$ ($1 \leq i, j \leq N$) について、うさぎ $i$ と $j$ の相性が整数 $a_{i,j}$ によって与えられます。
ただし、各 $i$ ($1 \leq i \leq N$) について $a_{i,i} = 0$ であり、各 $i, j$ ($1 \leq i, j \leq N$) について $a_{i,j} = a_{j,i}$ です。

太郎君は、$N$ 羽のうさぎたちをいくつかのグループへ分けようとしています。
このとき、各うさぎはちょうど $1$ つのグループに属さなければなりません。

グループ分けの結果、各 $i, j$ ($1 \leq i < j \leq N$) について、うさぎ $i$ と $j$ が同じグループに属するならば、太郎君は $a_{i,j}$ 点を得ます。
太郎君の総得点の最大値を求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 16$
• $|a_{i,j}| \leq 10^9$
• $a_{i,i} = 0$
• $a_{i,j} = a_{j,i}$

回答

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

int main() {
    int N;
    cin >> N;

    // 行列入力
    vector<vector<long long>> a(N, vector<long long>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> a[i][j];
        }
    }

    // 前計算: score[S]
    // 集合 S を「1つのグループ」にしたときのスコア合計
    vector<long long> score(1 << N, 0);
    for (int S = 0; S < (1 << N); S++) {
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                // i も j も S に含まれているなら加算
                if ((S & (1 << i)) && (S & (1 << j))) {
                    score[S] += a[i][j];
                }
            }
        }
    }

    // dp[S] := 集合 S を最適にグループ分けしたときの最大スコア
    vector<long long> dp(1 << N, 0);

    // 小さい集合から順に計算
    for (int S = 0; S < (1 << N); S++) {
        // 部分集合 T を列挙する定石テクニック
        // T = S から始めて、T = (T - 1) & S で更新すると、Sの部分集合のみを降順に走査できる
        // T = 0 になったら終了
        for (int T = S; T > 0; T = (T - 1) & S) {
            // 遷移: S の一部 T を「1グループ」として切り出し、
            // 残り (S ^ T) は計算済みの dp を使う
            dp[S] = max(dp[S], score[T] + dp[S ^ T]);
        }
    }

    // 全員 (mask = (1<<N)-1) のときの最大値
    cout << dp[(1 << N) - 1] << endl;

    return 0;
}

自分なりの解説

DPの遷移:dp[S] = 「集合$S$のうさぎたちを、最適なグループ分けにしたときの最大スコア」とする。Sが小さいので個々の全列挙は可能である。元の集合を集合 $S$ を、「ある1つのグループ $T$ 」と「残りのうさぎたちに分割することを考える。