EDPC U - Grouping

考え方

ABCでいうと、F問題級。

いわゆる bitDP。
グループ分けの状態を bit 全探索の要領で調べていく過程で動的計画法を用いる。

採用するうさぎ一覧を bit で管理し、それぞれについて以下の値を DP で求めていく。

• 全うさぎを同じグループに入れる場合の得点
• 複数グループに分ける場合の最大得点

前者は、ある $1$ 体以外の場合の得点をベースに、その $1$ 体を追加したときの得点変化を a を見て求める。
後者は、以下の $2$ つの値の和の最大値で求める。

• ある $1$ 体に加え何体かを同じグループに入れる得点
• 残りを複数グループに分ける最大得点

これで理論上は答えが求まるが、問題は計算量。
愚直にやると $2^N$ 通りの DP テーブルそれぞれの枠で後者の計算に $2^N$ かけて、$4^N$ 回のループになる。
$N=16$ だと $4^N=4294967296$ で、$1$ 秒 $1$ 億ループでは $43$ 秒かかってTLE。

というのは厳密には嘘で、実はC++なら実は定数倍を軽くできれば $N=16$ での $O(4^N)$ は何とか間に合う。
しかし、それはこの問題の意図するところではないので、ちゃんと高速化を考える。

k を j の全ての部分集合としてforループを回すときに、高速化するテクニックがある。
最初に k=j で初期化し、更新を k=(k-1)&j で行う。
すると、降順に進みながら部分集合でないものをまとめてスキップできるため、処理が高速になる。
この方法を使った場合の計算量は $O(3^N)$ となる。

入力例1での動作

入力を受け取る。

n: 3
a:
  {0, 10, 20}
  {10, 0, -100}
  {20, -100, 0}

まず、各集合を $1$ つのグループにした場合の得点を求める。

うさぎ $0,1$ を同じグループにすると $10$ 点である。
うさぎ $0,2$ なら $20$ 点である。
うさぎ $1,2$ なら $-100$ 点である。

$3$ 体全てを同じグループにすると、全ての組の得点を足すので $10+20-100=-70$ 点となる。

まとめると次のようになる。

次に、各集合を好きな数のグループに分けた場合の最大得点を求める。

集合 $S$ を考えるとき、$S$ の中で番号が最大のうさぎを $b$ とする。

$b$ を含むグループを $1$ つ決める。
そのグループに入れなかったうさぎたちの集合を $T$ とする。

すると、

• $S\setminus T$ は、$b$ を含む $1$ つのグループ
• $T$ は、好きな数のグループに分ける部分

になる。

したがって、候補となる得点は、この $2$ つの得点の和である。

$T$ を、$S$ から $b$ を除いた集合の全ての部分集合について試す。
その最大値が、$S$ を最適にグループ分けした得点となる。

例えば集合 $\{0,1\}$ を考える。
最大番号は $1$ である。

$1$ を含むグループを $\{0,1\}$ にする場合は $10$ 点である。
$1$ を含むグループを $\{1\}$ にする場合は、残りの $\{0\}$ の最大得点 $0$ を足して、合計 $0$ 点である。

したがって、$\{0,1\}$ の最大得点は $10$ となる。

同様に、

• $\{0,2\}$ の最大得点は $20$
• $\{1,2\}$ の最大得点は $0$

となる。

最後に、集合 $\{0,1,2\}$ を考える。
最大番号は $2$ である。

$2$ を含むグループの作り方ごとに、残りの集合の最大得点を足す。

この最大値は $20$ である。
したがって、答えは $20$。

注意点

答えは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。