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}

dp_full[i] を、集合 i に含まれるうさぎを全員同じグループにした場合の得点とする。
これは、すでに求めた集合にうさぎを $1$ 体追加し、そのうさぎと既存のうさぎの間の得点を加える。

たとえば、dp_full[7] を求めるときは、集合 {0, 1} にうさぎ 2 を追加する。

dp_full[3] = 10
a[2][0] = 20
a[2][1] = -100

dp_full[7] = 10 + 20 - 100 = -70

この入力例では、dp_full は次のようになる。

dp_full[0] = 0
dp_full[1] = 0
dp_full[2] = 0
dp_full[3] = 10
dp_full[4] = 0
dp_full[5] = 20
dp_full[6] = -100
dp_full[7] = -70

次に、dp_part[i] を、集合 i に含まれるうさぎを任意個数のグループに分ける場合の最大得点とする。

dp_part[7] を求めるときは、うさぎ 2 を含むグループを先に決める。
残りのうさぎについては、すでに求めた dp_part の値を使う。

うさぎ 2 を含むグループ: {2}
残り: {0, 1}
dp_full[4] + dp_part[3] = 0 + 10 = 10

うさぎ 2 を含むグループ: {0, 2}
残り: {1}
dp_full[5] + dp_part[2] = 20 + 0 = 20

うさぎ 2 を含むグループ: {1, 2}
残り: {0}
dp_full[6] + dp_part[1] = -100 + 0 = -100

うさぎ 2 を含むグループ: {0, 1, 2}
残り: {}
dp_full[7] + dp_part[0] = -70 + 0 = -70

この最大値を取るので、次の値になる。

dp_part[7] = 20

よって答えは $20$ である。

注意点

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

別解

特になし。