[AtCoder] ABC 142 E – Get Everything

2019年9月30日

問題

方針

考察

鍵 \( i \) は \( b_i\) 種類の宝箱を開けることができるので、鍵は鍵束であると見ることができます。全ての宝箱を開けられないときは、全ての鍵の集合に対して対応できない宝箱があるということなので、先にそれのチェックを行います。

また、鍵の使う順番によって費用が変化しないことに注目すると、ある鍵を使うか使わないかの \( 2 \) 通りが考えられるので、愚直に考えると、\( 2^{M} – 1\) のパターンを調べれば良いことが分かります。これでは、計算量が大きすぎるので別の方法を考えます。

bitDP

ある鍵を使ったときに遷移する状態を考えれば良いので、bitDP を行います。\( N \) 個の宝箱の状態を \( 2 \) 進数で表現すると、宝箱は開いているかいないかの状態があるので、全ての宝箱の状態は \( 2^N \) 通りで表現できます。

配列 \( d \) の添え字 \( i \) を \( 2 \) 進数で表現された宝箱の状態とします。例えば、\( 0 \) は全ての宝箱が閉じている状態であり、\( 3 \) は、 \( 2 \) 進数で表記すると、\( 11 \) なので、宝箱 \( 1, 2 \) が開いている状態です。配列 \( d \) は宝箱をその状態にするのに必要なコストの最小値とします。初期値は、\( d_0 = 0 \), \( d_i = \infty \ (i \neq 0) \) とします。

遷移の仕方は、鍵 \( i \) を順番に見ていきます。\( f_i \) を鍵 \( i \) が開けることができる宝箱を \( 2 \) 進数でしたものとします。全ての宝箱の状態 \( k \) に対して、\( t = f_i | k \) としたとき、

\[d_t = \min (d_t, d_k + a_i)\]

と更新します。\( t \) は宝箱の状態 \( k \) に対して、鍵 \( i \) を使ったときに遷移する状態となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N, M;
  cin >> N >> M;
  int a[M];
  int b[M];
  int f[M]{};
  int t = 0;
  int flag[N]{};
  for (int i = 0; i < M; i++) {
    cin >> a[i] >> b[i];
    for (int j = 0; j < b[i]; j++) {
      cin >> t;
      t--;
      flag[t] = 1;
      f[i] += (1<<t);
    }
  }
  // 全ての宝箱を開けることができるかをチェック
  for (int i = 0; i < N; i++) {
    if (flag[i] == 0) {
      cout << "-1\n";
      return 0;
    }
  }
  int l = (1<<N);
  int dp[l];
  int inf = 100000000;
  fill(dp, dp + l, inf);
  dp[0] = 0;

  for (int i = 0; i < M; i++) {
    for (int k = 0; k < l; k++) {
      int idx = k | f[i];
      dp[idx] = min(dp[idx], dp[k] + a[i]);
    }
  }
  cout << dp[l - 1] << "\n";
  return 0;
}