質問: 以下のコードのアルゴリズムの思考回路がよくわかりません。 ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。 また、どのようにすればこのような思考でコードをかけるのでしょうか? どなたか分かる方はいらっしゃるでしょうか? コード元: 第16回日本情報オリンピック 予選4 --- ``` #include #include using namespace std; int p[110000]; int sum[20][110000]; int sz[20]; int dp[1<<20]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i
回答: 1. このコードのアルゴリズムについて ### DPの漸化式について まずビットDPをいったん忘れて、普通のDPを考えてみます。解説にある通り > > dp[S] := (配置に使った種類の集合が S の時のそこまでで取り出す必要があるぬいぐるみの個数の最小値) > > > とします。`S`に新たにぬいぐるみ`j`を加える場合を考えると、 ``` dp[S∪{j}] = min( 他の順番で状態S∪{j}に至る場合の最小値, 状態Sに至るための最小値(=dp[S])+((Sに含まれるようなぬいぐるみの個数+1)番目から数えて(ぬいぐるみjの個数)番目までに含まれる、jではないぬいぐるみの数) ) ``` という風に計算できます。最終的に`dp[全てのぬいぐるみを含む集合]`が解になります。 ところが、配列の添え字は整数でなければならないので、整数を集合に対応させる方法が必要になります。 ### 集合を整数で表す方法 集合は、もし`i`番目の要素が含まれるなら`i`ビット目が立った整数として表現することができます。集合に対する操作もビット演算で表現できます。 以下は集合演算の例です。(以下、`n`, `m`を(集合を表す)整数とします) * 空集合 ... `0` * `n`と`m`の和集合 ... `n | m` * `n`と`m`の積集合 ... `n & m` * `n`に`i`番目の要素が含まれるか ... `(n & (1 << (i-1))) != 0)` 積集合の応用です。`1 << (i-1)`は`i`ビット目だけが立つ、すなわち`i`番目の要素のみを含む集合を表すので、これと元の集合との積を取って空集合にならないことを確認すればよいです。 * 1~bまでの要素をすべて含む集合 ... `(1 << b) - 1` `1 << b`でb+1ビット目のみが立ちます。これから1を引くことで下位bビット全てが1になります。 ### ビットDPについて さて、集合を整数で表せたので、配列の添え字として使うことができるようになりました。これが解説で言及されているビットDPです。コードでは以下の部分にあたります。 ``` for(int i=0;i<(1<