bitDPを調べたが分からなかった人への解説

1.初めに

こんにちはKNKMTです。競技プログラミングを主にやっています。
今回はbitDPについての話をしようと思います。

かくいう私もbitDPを学ぼうと思ったとき、たくさん記事を見たのですが、まったく分かりませんでした。(私の理解力が無いのが一番の原因)

今後、恐らく私のような人が出るだろうと考え、この記事を書こうと思いました。私自身、qiita初投稿なので、説明不足や分かりにくい部分が多々あると思います。すいません。

2.前提知識

• 動的計画法(ナップザック問題が理解できる程度)
• bit演算の知識(or,and演算子がわかる、bit全探索が書ける人を想定)
• bitDPというのをちょっと知っている(例えば、$O(2^n)$になることが多いなど)

bit演算についてはこれを参考にするとよいです。

3.本題の前に

どこかのサイトで見たのですが、

bitDP は 集合DP である。

これを、よく覚えておいてください。これが本質です。
bitDPはbit全探索までは使わなかった　(あまり意識しなかったというのが正確だが)　bitの別の利用方法があります。それは、「bitは集合を表すことができる」という点です。

正直、この点を理解すれば,他のbitDPについて解説している記事を読むとわかると思います。

どういうことか説明しましょう。例えば、A君、B君、C君、D君、E君、F君がいる全体で6人のグループがあります。今A君とC君がいます。ここで、D君とE君が合流すると、下の画像のようになります。

「何当たり前のこと言ってんだ。」と思う人もいるかもしれません。しかし、これをどのようにしてコンピューターの中で認識しましょう？

ここで使われるのがbitです。A,B,C,D,E,F君それぞれに「集合内に存在するか」ということを0か1で表し、それらを1列に並べ、それを2進数とみると整数として認識できます。
具体的な例を見て、確かめてみましょう。
合流する前は、A,C君がいるのでbitは
101000
になります。

一方で、合流した後はA,C,D,E君がいるので
101110
他の例を試してみればわかるのですがこれはor演算であるとわかります。

以上の例から、集合をbitで表せるということがわかると思います。

このことを理解できたと実感された方はほかの記事を読むといいと思います。なんとなくわかってくるはずなので。

典型例として、巡回セールスマン問題(TSP)を見てみましょう。さっきの例をA,B,C,D,E,F町とすると、

4.例題その1 Kotamanegi Online Judge No.70

では、実際に解いてみましょう。問題文は下にあります。

問題を強引に端折ると、
N種類のボタンがある、ボタンiをボタンjを押す前に使うと、$a_{ij}$の点がもらえる。得点を最大化してください。($a_{ij}$はN*Nの形式で与えられる。)

(※本来は、与えられた配列t[n]の合計から、得点を引いた値を最大化します。)

解法
基本的なbitDPは一つずつ集合に要素を追加していく遷移が多いです。

すでに、そのアルゴリズムを勉強したかをbitにして表す。
詳しくは、下のコードを見てください。

qiita answer　(1)

#include<bits//stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
#define rep(i,n) for(int i = 0;i<n;i++)
int main() {
    int n; cin >> n; vector<int> t(n); 
    vector<vector<int>> a(n, vector<int>(n));
    rep(i, n) cin >> t[i];
    rep(i, n) rep(j, n) cin >> a[i][j];
    vector<int> dp(1 << n, 1e9); dp[0] = 0;//初期化
    rep(bit, 1 << n) {
        rep(j, n) {
            if (!(bit >> j & 1)) {
                int sum = 0;
                rep(k, n) {
                    if (bit >> k & 1)sum += a[k][j];//ボタンを押していたら得点獲得
                }chmin(dp[bit | (1 << j)], dp[bit] + t[j] - sum);
            }
        }
    }cout << dp[(1 << n)-1] << endl;
}  

5.例題その２ ABC142 E GetEverything

前の問題の様に、一つだけ集合に併合して遷移していくものではなく、
複数の要素を持った集合を併合することによって、DPを遷移する問題です。
複数追加することになってもやることはそれほど変わりません。

qiita u.answer　(2)

#include<bits//stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int main() {
    int n, m,t,c; cin >> n >> m;
    vector<int> a(m), b(m), dp(1 << n, 1e9); dp[0] = 0;
    rep(i, m) {
        cin >> a[i] >> t; int bit = 0;
        rep(j, t) {
            cin >> c; c--; bit |= (1 << c);
        }b[i] = bit;
    }rep(bit, 1 << n) {
        rep(i, m) {
            chmin(dp[bit | b[i]], dp[bit] + a[i]);
        }
    }if (dp[(1 << n) - 1] != 1e9) cout << dp[(1 << n) - 1] << endl;
    else cout << -1 << endl;
}

6 O(3^n)のbitDP

今までのbitDPはbitの全列挙して遷移しているごとに大体$O(n) or O(1)$位かけたものを使っていましたが、各遷移ごとの計算量が、集合の部分集合の大きさとなるものもあります。(例えば、TSPの例だと、A~Fという町があるとして、A,C,Dを今の状態とすると、{φ},{A},{C},{D},{A,C},{A,D},{C,D},{A,C,D}の状態全てを考えるようなものです。イメージとしてはグループ分けみたいなものが多いです。)
要素の個数がnの集合の部分集合の個数が$2^n$で、$2^n$のDPを回すと、$4^n$になりそうな気がしますが、違います。なぜなら、現状態が{A}のみであるのと、{A,B,C,D,F}の場合では、考える遷移の数が全く違うからです。
例題としてはEDPC U - Groupingがいい問題だと思います。

7.演習したい人に

はまやんはまやんさんの素晴らしい記事によくまとめられています

次の問題が良いと思います。
例題1

ABC 180 E - Traveling Salesman among Aerial Cities
ABC 199 E - Permutation
ABC 190 E - Magical Ornament

例題2
PAST 1 I - 部品調達
JOI 2014 予選 D　部活のスケジュール表
(↑集合を使って遷移し、数え上げていく問題です。)

8.補足

例題では扱いませんでしたが、ほかにもドミノを敷き詰める系のbitDP(蟻本に載っている)などがあります。

9.最後に

「bitDPがわからなかった人への解説」というタイトルにしましたが、分かりにくいかもしれません。すいません。間違いや改善点、分からない点がありましたら、遠慮なくご指摘ください。(そもそもこんな拙い記事を読んでくれる人がいればの話ですが...)