AtCoder Beginner Contest 142 E - Get Everythingを解いた感想

実装にだいぶ時間がかかった。けどできたのでよし。実行時間800msecとかなりアルゴリズム的には良くないコードを書いてしまった。けどそれしか解法が思いつかんかったから仕方ない。

問題はこちらです。

atcoder.jp

宝箱が最大12個与えられる。そしてその宝箱を開ける鍵が最大1000個与えられる。鍵について使うコストと開けられる宝箱の番号が与えられる。最小で幾らのコストで宝箱を全て開けることができるかという問題。

解法

DPするんだろうなと思いつつ、結果DP。開ける宝箱は高々12個しかないので全探索できる(2^12通り）。そして左から何番目までの鍵を使えるかで1000通り。合計5000000回計算すれば終わる。

詳しい内容はコードを見て。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int m;
  cin >> m;
  vector<int> cost(m);
  bitset<12> initial("000000000000");
  vector<bitset<12>> key(m, initial);
  for(int i=0;i<m;i++) {
    int a, b;
    cin >> a >> b;
    for(int j=0;j<b;j++) {
      int c;
      cin >> c;
      c--;
      key[i].set(c);
    }
    cost[i] = a;
  }
  const int lim = pow(2, n);
  vector<vector<int>> dp(lim, vector<int>(m+1));
  for(int i=0;i<lim;i++) {
    for(int j=0;j<m+1;j++) {
      if(i == 0) dp[i][j] = 0;
      else if(j == 0) dp[i][j] = -1;
      else {
        bitset<12> bit(i);
        bitset<12> amp = (bit & key[j-1]);
        if(amp.none()) {
          dp[i][j] = dp[i][j-1];
          continue;
        }
        int idx = 0;
        for(int k=0;k<12;k++) {
          if(bit.test(k) && !key[j-1].test(k)) {
            idx += pow(2, k);
          }
        }
        if(dp[idx][j-1] == -1) {
          dp[i][j] = -1;
          continue;
        }
        int tmp = dp[i][j-1];
        if(tmp == -1) tmp = INT_MAX;
        dp[i][j] = min(cost[j-1] + dp[idx][j-1], tmp);
      }
    }
  }
  cout << dp[lim-1][m] << endl;
  return 0;
}