ツバサの備忘録

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

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

bitDP 動的計画法(DP) 前計算

問題
提出コード

解法

制約から見て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|と表現すると、部分集合Tは2^{|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です。

Sの部分集合列挙は、

for(int b = S; b > 0; --b &= S){
  hoge;
}

という感じでやるとできます。
桁が下の方から削除していくイメージです。

感想

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