ツバサの備忘録

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

Educational DP Contest / DP まとめコンテスト U - Grouping

問題
提出コード

解法

制約から見てbitDPです。

  • dp[S] = 現在グループを組めていないウサギの状態がSのときに、それ以降のグループ分けで得ることができる得点の最大値

とします。すると、Sの部分集合Tを用いて、
dp[S] = max(dp[S\setminus T ] + sum[T])
と書くことができます。
ただし、sum[T]は、Tというグループを作成したときに得られる得点です。これは、前計算によってO(2^{N}N^{2})で計算できます。
先ほどのDPの遷移の計算量を見積もってみます。
ある集合Sについて、残っているウサギの数を|S|と表現すると、部分集合T2^{|S|}通りあります。
残っているウサギの数が|S|となるような集合Sの選び方は_{N}C_{|S|}です。ここで、本来は|S|が0となるような選び方をしないのですが、計算をしやすくするために0も選ぶことができるとすると、|S|0からNまであり得ることに注意して、
\displaystyle \sum_{i=0}^{N} 2^{i} \  _{N}C_{i}
となり、これは
\displaystyle \sum_{i=0}^{N} 2^{i}  \times 1^{N-i} \times   _{N}C_{i}
であり、結局二項定理の式そのものなので、
(2+1)^{N} = 3^{N}
となります。
ということで、最初のDPの遷移はO(3^{N})で計算できるということがわかりました。
あとは、前計算とDPの遷移を行うことで、dp[S_{all}]を見れば答えがわかります(S_{all}は全てのウサギが入っている状態です)。初期状態は、ウサギが1羽の任意の集合Uに対して、dp[U] = 0です。

感想

だいぶ前に考察だけ終わらせておいて放置していた問題でした…
bitDPなのでやりたいことはほぼ覚えてました。一見O(4^{N})になりそうで、きちんと計算すると計算量が減るタイプの問題ですね。