2014 Yandex.Algorithm Elimination Stage, Round1 E - Burger Bar

問題概要

n 個の要素からなる数列 a が1つ与えられる.
以下を満たす集合 X のうち,最小の |X| をもとめよ.

  • X = {b_1, ..., b_k} とすると,任意の a の要素は,Xの要素のうちからいくつか選んで足し合わせて作ることができる(ただし,おなじ i に対して b_i を2回使うことはできない).

・制約
1 <= n <= 20
1 <= a_i <= 50

解法

a_i のサイズが高々50であるから,解の上界は6である.
50C5 = 2 * 10^6 ぐらいなので,5個までを適当に全探索しても間に合いそう.
多分条件を満たすXがたくさんあるので,条件を満たすかチェックする分のオーダーを入れてもそんなに遅くないと思う.

ソースコード

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<int> used;
    function<bool(int)> can_make = [&](int limit) {
        if((int)used.size() == limit) {
            vector<bool> dp(51, false);
            dp[0] = true;
            for(int i = 0; i < limit; ++i) {
                for(int j = 50 - used[i]; j >= 0; --j) {
                    dp[j + used[i]] = dp[j + used[i]] | dp[j];
                }
            }
            bool ok = true;
            for(int i = 0; i < n; ++i) {
                ok &= dp[a[i]];
            }
            return ok;
        } else {
            for(int i = (used.size() == 0 ? 1 : used.back() + 1); i <= 50; ++i) {
                used.push_back(i);
                if(can_make(limit)) {
                    return true;
                }
                used.pop_back();
            }
            return false;
        }
    };

    int ans = 6;
    for(int i = 1; i <= 5; ++i) {
        if(can_make(i)) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
}

感想

まさかEまできて全探索を書かされるとは思わなかった.