*BitDP [#j6df1af4]
このページは競技プログラミングに興味のある方向けにBitDPを簡単に説明するページです

**BitDPって何？ [#ya956ad3]

bitを用いたDPです

**そのまんまじゃん [#dbf04bd9]
DP自体が広い概念なので仕方ないです。

**どういうときに使うの [#ib4a98ea]
典型的なパターンとして、状態と整数を対応付けるときによく使います

**例題ください [#k5f70831]

整数が1つ記されたN枚のカードがある。~
このカードを二つの山に分けた時、両者の山にあるカードに記された整数の和が等しくなる分け方は何通りあるか~

**やり方は？ [#mde88399]

この問題を解くためには以下の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に「b,c」箱Bに「a,d,e」のカードが入っているという意味になります。~
つまり、(10進数で)25という数字と"箱Aに「a,e,d」箱Bに「b,c」のカードが入っている"状態が対応付けられたわけです。~
このようにあるオブジェクトのもつ状態が2つのみの場合、2進数表記することで整数と状態を対応付けることができ、列挙が容易になります。~
(もう少し一般化して、「あるオブジェクトのもつ状態がn通りの場合、n進数表記にすることで整数と状態を対応付けることが出来る」ともいえます)~
また、このように表記することでbit演算が有効に働く場合があり、そのような問題にこそBitDPを使うべきでしょう。~

**Bit演算が有効に働く問題をください [#j40f18cd]
そのうち載せます
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS