![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
このページは競技プログラミングに興味のある方向けにBitDPを簡単に説明するページです
bitを用いたDPです
DP自体が広い概念なので仕方ないです。
典型的なパターンとして、状態と整数を対応付けるときによく使います
整数が1つ記されたN枚のカードがある。
このカードを二つの山に分けた時、両者の山にあるカードに記された整数の和が等しくなる分け方は何通りあるか
この問題を解くためには以下の2つの部分を処理する必要があります
1：カードの分け方を効率よく列挙する
2：全探索すると2^(N-1)オーダーになるので、効率よく探索する
2に関しては通常のDPに譲るとして、ここでは1について考えましょう
と言っても単純で例えばカードを入れる箱をA,Bの二つ用意したとして「Aに入っている状態を0」「Bに入っている状態を1」と表現することとしましょう
そして、例えば5枚のカード(a, b, c, d, e)があるとして
・1桁目でaの状態を表す
・2桁目でbの状態を表す
・3桁目でcの状態を表す
・4桁目でdの状態を表す
・5桁目でeの状態を表す
というルールにしたとしましょう。
すると、例えば11001は箱Aに「a,e,d」箱Bに「b,c」のカードが入っているという意味になります。
つまり、(10進数で)25という数字と"箱Aに「a,e,d」箱Bに「b,c」のカードが入っている"状態が対応付けられたわけです。
このようにあるオブジェクトのもつ状態が2つのみの場合、2進数表記することで整数と状態を対応付けることができ、列挙が容易になります。
(もう少し一般化して、「あるオブジェクトのもつ状態がn通りの場合、n進数表記にすることで整数と状態を対応付けることが出来る」ともいえます)
また、このように表記することでbit演算が有効に働く場合があり、そのような問題にこそBitDPを使うべきでしょう。
そのうち載せます
