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で表せるということがわかると思います。
このことを理解できたと実感された方はほかの記事を読むといいと思います。なんとなくわかってくるはずなので。
4.例題その1 Kotamanegi Online Judge No.70
では、実際に解いてみましょう。問題文は下にあります。
解法
基本的なbitDPは一つずつ集合に要素を追加していく遷移が多いです。
すでに、そのアルゴリズムを勉強したかをbitにして表す。
詳しくは、下のコードを見てください。
#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を遷移する問題です。
複数追加することになってもやることはそれほど変わりません。
#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.演習したい人に
はまやんはまやんさんの素晴らしい記事によくまとめられています
次の問題が良いと思います。
例題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 部活のスケジュール表
(↑集合を使って遷移し、数え上げていく問題です。)
7.補足
例題では扱いませんでしたが、ほかにも$O(3^n)$のbitDPやドミノを敷き詰める系のbitDP(蟻本に載っている)などがあります。
8.最後に
「bitDPがわからなかった人への解説」というタイトルにしましたが、分かりにくいかもしれません。すいません。間違いや改善点、分からない点がありましたら、遠慮なくご指摘ください。(そもそもこんな拙い記事を読んでくれる人がいればの話ですが...)