ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC056 C - 部門分け

問題
提出コード
高速化がなかなか思いつきませんね…

解法

まずは、制約からbitDPをエスパーで思いつきます。
dp[s] = グループの状態がsのとき、これを分割したときに作成できるスコアの最大値
とします。sはビットにより表現できます。
sを分割して、ts-tに分けたときに、ts-tから任意に1人ずつ選んだ時の信頼度の総和をxとすると、この値だけスコアが下がることになります。
すると、
dp[s] = max(0,k-x+dp[t]+dp[s-t]) と表現することができます。
また、グループが1人の状態の場合は自動的に最大値は0になります。
答えは、全員が1つのグループになっている状態を表す状態をSとしたとき、dp[S]+kとなります。
あとは、xを高速に求めることができれば、満点を取ることができます。
sum[s] = グループの状態がsの場合、sの中での任意の2人に対する信頼度の総和
とすると、これはO(2^N  N^2)で求めることができます。
このとき、ss-ttに分割した場合のxは、
sum[t]+sum[s-t]-sum[s]
の計算をすることで、なんとO(1)で求めることができます。
あとは、上のDPを行うことで答えを求めることができます。