かしのブログ

競技プログラミングとか

AtCoder Regular Contest 056 C - 部門分け

AtCoder DP 部分集合の部分集合

問題

$N$ 人の社員をいくつかのグループに分けるときのスコアの最大値を求める。スコアは $(グループ数)\times K - (異なる部門に属する2人の間の信頼度の総和)$ で与えられる。

考察

要素数 $N$ の集合 $\mathcal{S}$ の部分集合の部分集合の列挙は $\mathcal{O}(3^N)$ でできる。

$\sum_{\mathcal{T} \in 2^\mathcal{S}} 2^{|\mathcal{T}|} = \sum_{k=0}^N \dbinom{N}{k} 2^k = (2+1)^N = 3^N$

$dp[\mathcal{S}] \triangleq$ 集合 $\mathcal{S}$ だけで問題を解いたときの解とする。 $|\mathcal{S}| = 1$ のとき、 $dp[\mathcal{S}] = K$ 。 $|\mathcal{S}| \geq 2$ のとき、

$dp[\mathcal{S} ] = \max_{\mathcal{T}\subset\mathcal{S}}$ $dp[\mathcal{T}] + dp[\mathcal{S} - \mathcal{T}] -$ $[\mathcal{S}-\mathcal{T}と\mathcal{T}の要素の信頼度の総和]$

で求められる。

$W(\mathcal{S}) \triangleq \mathcal{S}$ の全ての要素間信頼度の総和

とすると

$[\mathcal{S}-\mathcal{T}と\mathcal{T}の要素の信頼度の総和] = W(\mathcal{S}) - W(\mathcal{S-T}) - W(\mathcal{T})$

より、 $W(\mathcal{S})$ を前処理で計算しておくとこの問題を解ける。これはDFSで $\mathcal{O}(N\cdot 2^N)$ で求められる。

実装

感想

要素数 $N$ の集合の部分集合の部分集合の列挙が $\mathcal{O}(3^N)$ になることは覚えておきたい。