EDPC-U「Grouping」 #C++

Grouping

解法

dp[i]: この集合の組み合わせの数とする。
遷移はdp[これから使用する | 使用済み] += dp[使用済み]って感じ。
あと、グループ分けした時の合計スコアを$O(1)$で参照できるようにする。
計算量は$O(3^N)$

コード

スコアを求める部分を$O(N^2)$部分を毎回求めてると$O(3^NN^2)$になる。これは$11019960576$ステップくらい回すので間に合わない。
なのでスコア部分をあらかじめ計算しておき$O(1)$で参照できるようにすることで計算量を$O(3^N)$にできた。計算ステップは$43046721$回くらいなので余裕で間に合う

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

#define int long long

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }

int N;
int a[20][20];
int dp[1<<16]; // dp[i]: iの立っているビットを使用したときの組み合わせの数
int USE[1<<16]; // USE[i]: iで立ってるビットを同じグループとしたときのスコア

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      scanf("%lld", &a[i][j]);
    }
  }

  // 使用したビットに対応するスコアをあらかじめ計算しておく
  for (int use = 0; use < (1 << N); use++) {
    int score = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i; j < N; j++) {
        if (((use >> i)&1) and ((use >> j)&1)) {
          score += a[i][j];
        }
      }
    }
    USE[use] = score;
  }

  // DP
  for (int used = 0; used < (1 << N); used++) { // 使用済みのビット
    int unused = used ^ ((1 << N) - 1); // 未使用のビット
    for (int use = unused; use > 0; use=(use-1)&unused) { // unusedの部分集合を列挙
      if (!(use > used)) continue;
      chmax(dp[use | used], dp[used] + USE[use]);
    }
  }

  cout << dp[(1<<N)-1] << endl;

  return 0;
}

メモ

twXIIveの類題としててんぷらさんに投げてもらった問題。大体あれと同じ感じで解ける。使用したビットに対応するスコアを$O(1)$ にする分Groupingの方が少し難しい。