けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 142 E - Get Everything (500 点)

個人的には bitDP は「順列を全探索するもの」というイメージがあるけど、今回はそれとはまた違う bitDP という感じ!

問題へのリンク

問題概要

 N 個の宝箱がある。宝箱を開けるための鍵が  M 個あって、それぞれの鍵はいくつかの宝箱に対応している。鍵  i を用いるのに  a_i だけコストがかかり、それを用いることで対応している宝箱がすべて開く (すでに開いている宝箱は変化しない)。

最終的にすべての宝箱を開けるのに必要な最小コストを求めよ。

制約

  •  1 \le N \le 12
  •  1 \le M \le 1000

考えたこと

見るからに bitDP!!!
bitDP は「ある集合の部分集合を添字とした DP」ができる!!!

今回の DP は

  • dp[ i ][ S ] := 最初の i 個の鍵からいくつか選んで、開いた宝箱の集合が S で表されるような場合についての、最小コスト

という感じでうまくいく。集合 S はビットで表すのが便利で、たとえば  N = 3 のときは

  • S = 0 ( { } )
  • S = 1 ( {0} )
  • S = 2 ( {1} )
  • S = 3 ({1, 0} )
  • S = 4 ( {2} )
  • S = 5 ( {2, 0} )
  • S = 6 ( {2, 1} )
  • S = 7 ( {2, 1, 0} )

という 23 = 8 通りの値をとる。宝箱が  N 個なら、S は  0, 1, \dots, 2^{N}-1 2^{N} 通りの値をとる。

bitDP の更新

部分集合をビットで表す考え方については、以下の記事にまとめた。

qiita.com

今回必要になる知識は

  • 集合 S (に対応するビットは s) と集合 T (に対応するビットは t) に対して
  • S と T の和集合 S  \cup T は a | b で表せる

という感じ。これからナップサック DP と同様に、 dp[ i ][ s ] ( s = 0, 1, \dots, 2^{N}-1) の値がわかってることを前提として、dp[ i + 1 ][ s ] ( s = 0, 1, \dots, 2^{N}-1) の値を更新していく。ナップサックでは s の部分は「ナップサックにすでに入っている品物の重さの合計値」だったが、今回は「すでに開いている宝箱の部分集合」である。

i 番目の鍵を使わないとき

単純に

  • chmin(dp[ i + 1 ][ s ], dp[ i ][ s ])

となる。chmin についてはここを参照。

i 番目の鍵を使うとき

i 番目の鍵に対応している宝箱の集合をビット c[ i ] で表すことにすると、

  • chmin(dp[ i + 1 ][ s | c[ i ] ], dp[ i ][ s ] + a [ i ])

となる。

初期条件

初期条件は単純に

  • dp[ 0 ][ 0 ] = 0 (それ以外のところは INF に初期化)

で OK

計算量

計算量は  O(M2^{N}) で十分間に合う。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }


const long long INF = 1LL<<60;
 
int N, M;
vector<long long> a, b;
vector<int> c;
 
 
long long dp[1100][5000];
 
int main() {
    int N, M; cin >> N >> M;
    vector<long long> a(M), b(M), c(M, 0); // c はビットで表す
    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i];
        for (int j = 0; j < b[i]; ++j){
            int t; cin >> t; --t;
            c[i] += (1<<t);
        }
    }
 
    for (int i = 0; i < 1100; ++i) for (int j = 0; j < 5000; ++j) dp[i][j] = INF;
    dp[0][0] = 0;
    
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < (1<<N); ++j) {
            chmin(dp[i+1][j], dp[i][j]);
            
            int nj = j | c[i];
            chmin(dp[i+1][j | c[i]], dp[i][j] + a[i]);
        }
    }
 
    cout << (dp[M][(1<<N)-1] < INF ? dp[M][(1<<N)-1] : -1) << endl;               
}