AtCoder Regular Contest 056 C - 部門分け

問題

　 $N$ 人の社員をいくつかの部門に分けることを考える。社員 $i$ と $j$ の間には信頼度 $w_{i,j}$ が定まっており、部門分けのスコアは $K$ を定数として $\displaystyle (部門の数)\times K - (異なる部門に属する2人の間の信頼度の総和)$

　として計算される。スコアの最大値を求めよ。

解法

　 $dp[S]$ を社員の集合 $S$ に対する問題の答えとする。 $S$ の部分集合を $T$ として、これが一つの部門であるとすると

$dp[S] = dp[S - T] + K + (S-TとTの間の信頼度の総和)$

　となる(解説を参照のこと)。これは $S$ に含まれる社員間の信頼度の総和から、 $S-T$ に含まれる社員間の信頼度の総和および $T$ に含まれる社員間の信頼度の総和を引いたものとなる。つまり任意の部分集合について社員間の信頼度の総和をあらかじめ $O(2^n)$ で求めておけば、DPの遷移は $O(1)$ で行える。

　このDPの計算量は $O(3^n)$ となるため間に合う。

反省

　1時間59分(2WA)でAC。30分そこそこで部分点解法を書いたあとはあまり考察が進まず。集合に対してDPを考えるというのも典型なんだろう。しっかりできるようになっておきたい。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> w(N, vector<ll>(N));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            cin >> w[i][j];
        }
    }

    //各部分集合ごとの信頼度の和
    vector<ll> sum(1LL << N, 0);
    for (ll i = 0; i < (1LL << N); i++) {
        vector<ll> members;
        for (ll j = 0; j < N; j++) {
            if (i & (1LL << j)) {
                members.push_back(j);
            }
        }
        for (ll j = 0; j < members.size(); j++) {
            for (ll k = j + 1; k < members.size(); k++) {
                sum[i] += w[members[j]][members[k]];
            }
        }
    }

    //dp[i] := 頂点集合iに対する答え
    vector<ll> dp(1LL << N, 0);
    for (ll i = 1; i < (1LL << N); i++) {
        for (ll j = i; j > 0; j = (j - 1) & i) {
            dp[i] = max(dp[i], dp[i ^ j] + K - (sum[i] - sum[i ^ j] - sum[j]));
        }
    }
    cout << dp[(1LL << N) - 1] << endl;
}