

以下のコードのアルゴリズムの思考回路がよくわかりません。

ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません（なぜDPが成立するのかがわからない）。  
また、どのようにすればこのような思考でコードをかけるのでしょうか？  
どなたか分かる方はいらっしゃるでしょうか？

コード元： [第16回日本情報オリンピック 予選4](https://www.ioi-
jp.org/joi/2016/2017-yo/2017-yo-t4/review/2017-yo-t4-review.html)

* * *
[code]

    #include<stdio.h>
    #include<algorithm>
    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<a;i++){
            scanf("%d",p+i);
            p[i]--;
            sum[p[i]][i+1]++;
            sz[p[i]]++;
        }
        for(int i=0;i<b;i++)for(int j=0;j<a;j++){
            sum[i][j+1]+=sum[i][j];
        }
        for(int i=0;i<(1<<b);i++)dp[i]=999999999;
        dp[0]=0;
        for(int i=0;i<(1<<b);i++){
            int pos=0;
            for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];
            for(int j=0;j<b;j++){
                if(i&(1<<j))continue;
                dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j][pos]);
            }
        }
        printf("%d\n",dp[(1<<b)-1]);
    }
    
[/code]


CC BY-SA 4.0
2018-10-27T05:55:36.287
49702
2018-10-30T01:11:49.807
2018-10-30T01:11:49.807
3060
24617
question
c++ アルゴリズム c++11
ビットDPの思考回路について


## 1\. このコードのアルゴリズムについて

### DPの漸化式について

まずビットDPをいったん忘れて、普通のDPを考えてみます。解説にある通り

> dp[S] := (配置に使った種類の集合が S の時のそこまでで取り出す必要があるぬいぐるみの個数の最小値)

とします。`S`に新たにぬいぐるみ`j`を加える場合を考えると、

[code]

    dp[S∪{j}] = min(
                 他の順番で状態S∪{j}に至る場合の最小値, 
                 状態Sに至るための最小値(=dp[S])+((Sに含まれるようなぬいぐるみの個数+1)番目から数えて(ぬいぐるみjの個数)番目までに含まれる、jではないぬいぐるみの数)
                )
    
[/code]

という風に計算できます。最終的に`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です。コードでは以下の部分にあたります。

[code]

    for(int i=0;i<(1<<b);i++){
        int pos=0;
        for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];
        for(int j=0;j<b;j++){
            if(i&(1<<j))continue;
            dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j][pos]);
        }
    }
    
[/code]

上のコードでは`i`が集合に対応し、これが`0`から`(1<<b)-1`(=b桁の1)まで動くことで、「b個のぬいぐるみの集合」の全ての部分集合を列挙しています。

次に内側のforを見てみます。

[code]

    for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];
    
[/code]

では集合`i`に含まれるようなぬいぐるみ`j`について個数を`pos`に足していっています。すなわち`i`に含まれるようなぬいぐるみの個数を計算しています。

次のforがDPの核ですが、`j`はぬいぐるみを表しています。それが`0`から`b-1`まで動くことで、個々のぬいぐるみに対する処理を実現しています。

[code]

    for(int j=0;j<b;j++){
        if(i&(1<<j))continue;
        dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j][pos]);
    }
    
[/code]

まず集合`i`にぬいぐるみ`j`が既に含まれる場合はスキップしています。残りが上で書いた`dp[S∪{j}]`の計算部分です。ここは累積和の使い方が分かっていれば理解できると思います。

ところでこのビットDPの良いところは集合を整数で表現したとき、`S <=
S∪{j}`が成立しているという点です。上のコードで`i`は0から単純に増やしていっただけですが、`dp[S∪{j}]`を計算する時点で、`dp[S]`が求まっているので都合がよいです。

## 2\. どのようにすればこのような思考でコードをかけるのか

というと難しいですが、ビットDP自体はよく知られたテクニックですので、特に状態が小さな集合の時などにこの手法が候補として挙がってくると思います。


CC BY-SA 4.0
2018-10-28T02:37:02.107
49719
2018-10-29T12:16:42.710
2018-10-29T12:16:42.710
13199
13199
49702
answer