mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 056 C - 部門分け

うーん, 80 点はほしかったかも。

解法

bitDP します。

dp[state] = (state にあるものをうまく使ったときの最大スコア) とします。このとき, dp の更新は, state から適当な集団(state2 とする)を取り出して, 集合を state2 と state^state2 に分けたとき, state2 はこれからまださらに分割するとして, state^state2 はもう一つのグループとして確定させます。このときグループが一つ増えているので, スコアとしては K 増えますが, state2 と state^state2 に分けたことで減る分も考慮しないといけません。そこで,

dp[state] = max(K+dp[state2]-(state2 と state^state2 で減る分))

という漸化式が立ちます。この漸化式で問題なのは,

  • state から state2 を列挙するのを高速でやらないといけない
  • 二つの部分集合でかかるコストを高速で計算しないといけない

の 2 点です。

前者は, 結構いろんなところで出ている 4^n を 3^n にするテクニックです。例えばこんなところ
mayokoex.hatenablog.com
蟻本の 144p に書いてあるやつです。

後者は, memo[s] = (集合 s 内における信頼度の総和) というのを定義しておく(定義するのは遅くても O(2^n * n^2) とかでできる)と, (集合 s1 と集合 s2 の間の信頼度の総和) は memo[s1|s2] - memo[s1] - memo[s2] とすれば O(1) で計算できます。

後者全然気づかなかったし頭良い。

const int MAXN = 18;
const ll INF = 1ll<<55;
ll W[MAXN][MAXN];
ll memo[1<<MAXN];
ll dp[1<<MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        cin >> W[i][j];
    }
    for (int s = 0; s < 1<<N; s++) {
        for (int i = 0; i < N; i++) for (int j = i+1; j < N; j++) {
            int si = ((s>>i)&1);
            int sj = ((s>>j)&1);
            if (si & sj) {
                memo[s] += W[i][j];
            }
        }
    }
    for (int state = 0; state < 1<<N; state++) {
        int sub = state;
        do {
            if (sub != 0) {
                dp[state] = max(dp[state], K+dp[state^sub]-memo[state]+memo[sub]+memo[state^sub]);
            }
            sub = (sub-1)&state;
        } while (sub != state);
    }
    cout << dp[(1<<N)-1] << endl;
    return 0;
}