ICPC国内予選2019 C問題：天秤

問題. 天秤

$n$ 個の薬品と $m$ 個の分銅の重さが与えられる． $i$ 番目の薬品の重さは $a_i$ で， $j$ 番目の分銅の重さは $w_j$ である．すべての薬品に対して天秤が釣り合うような分銅の置き方が存在するか判定せよ．ただし，釣り合わないときは任意の重さの分銅を 1 つだけ追加することができる．追加して釣り合うことができる分銅が複数ある場合は重さが最小のものを答えよ．

制約： $1 \le n \le 100$ ，　 $1 \le m \le 10$ ，　 $1 \le a_i \le 10^9$ ，　 $1 \le w_i \le 10^8$

解法．全探索

$i$ 番目の薬品に対して釣り合うような分銅の置き方が存在するとき，各 $j$ に対してある $c_j \in \{-1, 0, 1\}$ が存在して $a_i = \sum_{j = 1}^m c_j \cdot b_j$ を満たす．このとき， $c_j$ が -1 のとき $j$ 番目の分銅は薬品と同じ側に置かれ， 0 のとき使用しなく，1 のとき薬品と反対の側に置くことを表している．したがって右辺の値の集合 $W = \{\sum_{j = 1}^m c_j \cdot b_j \mid c_j = -1, 0, 1\}$ を $O(3^m)$ 時間で全列挙して，各薬品の重さ $a_i$ に対して $a_i \in W$ かどうかを判定すればよい．

次に，与えられた分銅ではすべての薬品に対して釣り合うような置き方が存在しない場合を考える．ここで， $i$ 番目の薬品が釣り合うような分銅の置き方がないとする．すなわち， $a_i \notin W$ である． $i$ 番目の薬品が釣り合うように追加する分銅の重さの候補の集合は $A = \{\| a_i - w \| \mid x \in W\}$ である． $A$ の各重りについて追加してすべての薬品を釣り合わせることができるかを判定すれば答えが求まる．

計算時間： $O(n \cdot 3^m)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void enumerateWeight(const int idx, ll sum,
                     unordered_set<ll> &comb, const vector<int> &w) {
    if (idx < 0) {
        comb.insert(sum);
        return ;
    }

    for (ll select = -1; select <= 1; ++select)
        enumerateWeight(idx - 1, sum + select * w[idx], comb, w);
}

int solve(const int n, const int m) {
    // Input
    vector<int> a(n), w(m);
    for (auto &a_i : a) cin >> a_i;
    for (auto &w_i : w) cin >> w_i;

    unordered_set<ll> comb;
    enumerateWeight(m - 1, 0, comb, w);

    bool can_measure = all_of(a.begin(), a.end(), [&comb](int a_i) { return comb.count(a_i); });
    if (can_measure) return 0;

    ll min_add_w = LLONG_MAX, idx = 0;
    while (idx < n && comb.count(a[idx])) ++idx;

    for (ll sum : comb) {
        ll add_w = abs(sum - a[idx]);
        can_measure = all_of(a.begin(), a.end(), [&comb, &add_w](int a_i) {
                return comb.count(a_i) || comb.count(a_i - add_w) || comb.count(a_i + add_w);
            });

        if (can_measure) min_add_w = min(min_add_w, add_w);
    }

    return min_add_w < LLONG_MAX ? min_add_w : -1;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    int n, m;
    while (cin >> n >> m, n) cout << solve(n, m) << '\n';

    return 0;
}