BitDP

BitDP †

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

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

Bit演算が有効に働く問題をください †

そのうち載せます http://abc041.contest.atcoder.jp/tasks/abc041_d