Skip to main content
集合を整数で表す方法について加筆
ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

DPの漸化式について

これところが、配列の添え字は整数でなければならないので、整数集合に対応させる方法が必要になります。

集合を整数で表す方法

集合は、もしi番目の要素が含まれるならiビットDP目が立った整数として書い表現することができます。集合に対する操作もビット演算で表現できます。

以下は集合演算の例です。(以下、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です。コードでは以下の部分でしたにあたります

集合は、もしぬいぐるみjが含まれるならjビット目が立った整数として表現されています。例えば0が表すのは集合は空集合です。

また集合に対する操作はビット演算で表現できることに注意してください。(和集合は|で、積集合は&で、ある要素が含まれるかは積集合を応用して&で、といった具合です。)

これをビットDPとして書いたのがコード以下の部分でした

集合は、もしぬいぐるみjが含まれるならjビット目が立った整数として表現されています。例えば0が表すのは集合は空集合です。

また集合に対する操作はビット演算で表現できることに注意してください。(和集合は|で、積集合は&で、ある要素が含まれるかは積集合を応用して&で、といった具合です。)

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です。コードでは以下の部分にあたります

変数i -> j
ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

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

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

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

ソース リンク
letrec
  • 3,170
  • 1
  • 15
  • 34

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

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

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

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

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

という風に計算できます。最終的に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]);
    }
}

集合は、もしぬいぐるみjが含まれるならjビット目が立った整数として表現されています。例えば0が表すのは集合は空集合です。

また集合に対する操作はビット演算で表現できることに注意してください。(和集合は|で、積集合は&で、ある要素が含まれるかは積集合を応用して&で、といった具合です。)

上のコードでは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∪{i}が成立しているという点です。上のコードでiは0から単純に増やしていっただけですが、dp[S∪{j}]を計算する時点で、dp[S]が求まっているので都合がよいです。

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

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