ARC056 C. 部門分け
問題
N人の社員をいくつかの部門に分ける。
社員iと社員jの間には、信頼度w_ijがあり、部門に分けたときのスコアを「(部門の数)*K - 異なる部門に属する2人の間の信頼度の合計」とする。
スコアが最大になるように部門分けをした場合のスコアを返せ。
制約
- 1 <= N <= 17
- 1 <= w_ij <= 10^6
- w_ii = 0
- w_ij = w_ji
- 1 <= K <= 10^6
解法
各社員をbitで表現して、すでに割り当て済みの部分を1、そうでないものを0として考える。
dp[S] := 状態がSのときのスコアの最大値
とすると、dp[S]は、部門数が1の場合か、Sの1の部分が2つに分けられたTとRの組み合わせから再帰的に求められる。
例えば、S=1100111の場合、1つの分け方としてT=10xx110とR=01xx001のようなものが考えられるが、このTとRから構成された場合のSでのスコアは、「dp[T] + dp[R] - TとR間の信頼度合計」のように求められる。
SからTとRのような部分集合は、O(3^N)で列挙できるので、「TとR間の信頼度合計」が高速に求められればよい。
「TとR間の信頼度合計」は、「Sで1になっている社員間の信頼度合計」から、「Tで1になっている社員間の合計」と「Rで1になっている社員間の合計」を引いたもので求められるので、前計算O(2^N * N^2)で用意しておけば、O(1)で計算できる。
