AtCoder Regular Contest 056 C - 部門分け

問題

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

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

解法

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

 {\displaystyle 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;
}