ひらめの日常

日常のメモをつらつらと

AtCoder: ABC142-E Get Everything (500)

問題はこちら

atcoder.jp

 1...N までの箱がある。 i 個目の鍵のコストは  a_i であり、 b_i 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は  -1 を出力せよ。

考え方

まず、これは割と複雑な遷移をすることが分かる。一つの鍵を使うとどうなるか?というと、前の状態から、 b_i この箱が空いた状態に遷移する。

この図は解説放送より引用

f:id:thescript1210:20190929134425p:plain:w500

さらに今回は  1 \leq N \leq 12 なので、各々の鍵を使ったか使ってないかの  2 ^ N 通りの状態を管理することが可能。

次に、状態をどうやって管理するか?という問題になる。ここではbit列を使って管理すると良い。(bit全探索とかやってる時も基本的には同じような考え方で使っている。)

  •  c _  {ij} を開けることができる ->  c _ {ij} bit目のフラグを立てることができる。
  •  i が開けることのできる箱の集合 -> 全ての  c_i の和集合。
  •  i が空いている状態 ->  i bit目のフラグが立っている。

よって、DPで解くことを考える。

  •  dp[s] : 集合 s の宝箱を開ける最小コスト
  • 遷移元 : 全ての集合
  • 遷移先 : s と 鍵が開けられる集合 の和集合

これは、計算量  O(M \times 2 ^ N ) で間に合う。

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> key;
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        ll s = 0;
        rep(j, b) {
            ll c;
            cin >> c;
            c--;
            s |= 1 << c;
        }
        key.emplace_back(s, a);
    }
    ll pow2 = 1 << n;
    vector<ll> dp(pow2, ll_inf); // dp[i]: 集合iの宝箱を開ける最小コスト
    dp[0] = 0;

    rep(s, pow2) {
        rep(i, m) {
            ll t = s | key[i].first; // 遷移先
            ll cost = dp[s] + key[i].second;
            dp[t] = min(dp[t], cost);
        }
    }
    ll ans = dp.back();
    if (ans == ll_inf) ans = -1;
    cout << ans << '\n';
    return 0;
}

Submission #7781420 - AtCoder Beginner Contest 142

別解

こちらを参考にさせていただきました。

Submission #7758800 - AtCoder Beginner Contest 142

空集合から、 2 ^ {N-1} の状態へと遷移するグラフを考えてみると、以下のように言い換えることができる。

  • 頂点は、 0...2 ^ {N-1} まである。
  •  i\ (1...m)は、
    • 今の状態を  s とすると、s と 鍵iが開けられる集合 の和集合 へと遷移する。
    • そのコストは  a[i] である。
  • このようなグラフで、頂点 0 から  2^{N-1} へと遷移する最短路を求めよ。

こうなると、ダイクストラ法などを使って解くことができる。

ポイントとして、辺の from, to が明示的に与えられるわけではないので、自分で全ての集合からどの集合へ遷移するかを管理し直さなくてはいけない。

計算量は、頂点数  2 ^ {N} 、辺の数  M \times 2 ^ {N} より、 O(M \times 2 ^ {N} \times log(2 ^ {N})) で間に合う。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using P = pair<ll, ll>;
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

struct edge {
    ll from, to, cost;

    edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
};

class DAG {
private:
    ll v;
    vector<vector<edge>> table;
    vl d;
public:
    // v: 頂点数
    explicit DAG(ll v) : v(v) {
        table.resize(v);
        d.resize(v, ll_inf);
    }

    void add(ll from, ll to, ll cost = 1) {
        edge e1(from, to, cost);
        table[from].emplace_back(e1);
    }

    // O(e * logv)
    vl dijkstra(ll s) {
        // pairを使っているのは、比較関数を利用するため
        priority_queue<P, vector<P>, greater<>> que;
        d[s] = 0;
        que.push(P(0, s));

        while (!que.empty()) {
            P p = que.top();
            que.pop();
            ll min_v = p.second;
            if (d[min_v] < p.first) continue;
            for (const auto &ele: table[min_v]) {
                if (d[ele.to] > d[min_v] + ele.cost) {
                    d[ele.to] = d[min_v] + ele.cost;
                    que.push(P(d[ele.to], ele.to));
                }
            }
        }
        return move(d);
    }
};

int main() {
    ll n, m;
    cin >> n >> m;
    DAG dag(1 << n);

    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        ll s = 0;
        rep(j, b) {
            ll c;
            cin >> c;
            c--;
            s |= 1 << c;
        }

        rep(j, 1 << n) {
            dag.add(j, j | s, a);
        }
    }
    vl ans = dag.dijkstra(0);
    if (ans.back() == ll_inf) cout << -1 << '\n';
    else cout << ans.back() << '\n';

    return 0;
}

Submission #7781587 - AtCoder Beginner Contest 142