Educational DP Contest U コード 問題 BitDP を使う. うさぎの集合 \(S\) をグループ分けしたときの相性の合計の最大を \(C(S)\) とすると, \[C(S) = \max_{T \subset S} (C(T) + C(S \setminus T))\] となる. これをそのまま計算すると \(O(4^N)\) となるが, ある集合の部分集合を列挙する部分でうまく工夫すると \(O(3^N)\) に落とすことができる. よって計算量は \(O(3^N)\) である.