yukicoder No.519 アイドルユニット

問題

N人(2の倍数)のアイドルがいる。
全員ペアを組ませて売り出したい。
しかし、ペアには相性度が決まっており、すべてのペアの相性度の合計値が最大になるようにしたい。
相性度の合計の最大値を返せ。

制約

1 <= N <= 24
0 <= 各ペアの相性度 <= 1000

解説

一般的には、グラフの重み付きマッチングの問題らしい。
ここでは、各アイドルがペアを組んでいるかどうかを状態として持つbitDPを考える。

単純に考えると、「各状態でペアを組んでいないアイドル2人を選んで、状態を更新」するように計算する。

int N;
int cost[30][30];

int dp[1<<25];

int main(){
  cin >> N;
  rep(i,N){
    rep(j,N){
      cin >> cost[i][j];
    }
  }

  rep(i,1<<25) dp[i] = -1;
  dp[0] = 0;

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
    }
  }
  cout << dp[(1<<N)-1] << endl;
  return 0;
}

これだとO(2^N * N^2)でTLEしてしまう。

実は上記のループは無駄なところがある。
状態が「100100」の場合を考える。
(この状態でjとkのループでは、「1**100」「1*01*0」「1*010*」「10*1*0」「10*10*」「1001**」を列挙して状態を更新している。)
ここで、
「100100」から「110110」と遷移して「111111」に至るケースと、
「100100」から「101101」と遷移して「111111」に至るケースでは、
同じペアの組み方なのに、2回計算してしまっている。

ペアの推移的には、
(0,3)->(0,3)(1,4)->(0,3)(1,4)(2,5)
(0,3)->(0,3)(2,5)->(0,3)(1,4)(2,5)
のような感じ。

このような場合、同じペアの組み方をするのは1通りだけ考えればよいので、状態の中でまだペアを組んでいないアイドル(状態が0のところ)を一人選んで、そのアイドルを必ず取る場合を考えて、そのペア候補だけ(kのループ)を考えればよい。

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
      break; //これを入れるだけ
    }
  }

計算量は、O(2^N * N)になり、間に合う。