【ABC142】E - Get Everything

atcoder.jp

解法

それぞれの鍵を買うか否かの選択をM回することになるので、愚直に全探索しようとするとO(2^M)になるが、制約的に時間が足りない。
そこでDPができないかを考えてみる。
愚直解がO(2ⁿ)になってしまう時、DPを使うと無駄な計算を省いて高速化できることがよくある。

次のDPを考える。

dp[i][S] ← i番目までの鍵を見ていった時、既に開けることができる宝箱の集合S

状態として、既に開けることができる宝箱の集合を持つ必要がある。
集合を状態として持つDPは、bitDPと呼ばれる。
なぜbitなのかというと、集合に含まれているかどうかを2進数で表現するから。
下からi番目のbitが1であるとき、集合にiが含まれていることを表す。

DPは次のように遷移する。

• i番目の鍵を買わない時
  • dp[i + 1][S] ← min(dp[i + 1][S], dp[i][S])
• i番目の鍵を買う時 (xをi番目の鍵で開けることができる宝箱の集合とする)
  • dp[i + 1][S ∪ x] ← min(dp[i + 1][S ∪ x], dp[i][S] + a[i])

初期状態では、どの宝箱も開けることができないので、
dp[0][0] ← 0
それ以外 ← INF
とする。

そして、全ての宝箱を開ける必要があるので、 答えはdp[M][2^N-1]になる。

実装

C++だと2^Nは、1<<Nで表すことができる。

int main(){
    int N, M;
    cin >> N >> M;
    vector<ll> a(M), b(M);
    vector<vector<ll>> c(M);
    REP (i, M) {
        cin >> a[i] >> b[i];
        c[i].resize(b[i]);
        REP (j, b[i]) cin >> c[i][j];
    }

    // dpテーブル
    vector<vector<ll>> dp(M+1, vector<ll>((1 << N), INF));
    dp[0][0] = 0;

    REP (i, M) {
        REP (j, (1 << N)) {
            // i番目の鍵を買わない場合
            chmin(dp[i+1][j], dp[i][j]);

            ll x = j;
            REP (k, b[i]) {
                // c[i][k]を集合xに含める(既に含まれている場合、何もしない)
                x |= (1 << (c[i][k]-1));
            }
            // i番目の鍵を買う場合
            chmin(dp[i+1][x], dp[i][j] + a[i]);
        }
    }

    cout << (dp[M][(1<<N)-1] == INF ? -1 : dp[M][(1<<N)-1]) << endl;

    return 0;
}