1

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

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

コード元: 第16回日本情報オリンピック 予選4


#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]);
}

1 件の回答 1

1

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
  • nmの和集合 ... n | m
  • nmの積集合 ... n & m
  • ni番目の要素が含まれるか ... (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<<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]);
    }
}

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

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

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

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

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

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]);
}

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

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

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

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。