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まできて全探索を書かされるとは思わなかった.