CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy 46 Div. 1.5 C. Set Subtraction

CS Academy

感想

ちょっと応用できそう。

解法

まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補としてありうるもの、すなわち$\ A_{n - 1} - A_i (i = 0, 1, ..., n - 2)\ $だけをチェックすれば良い。重複をなくせるようにsetにいれた。

$\ X\ $を固定すると、ある数$\ a\ $に対して、そのペアとなる数が$\ a + X\ $と定まる。よってあらかじめすべての数の出現回数をmapなどで数えておいて、小さい数から順に$\ A_i\ $と$\ A_i + X\ $の回数を$\ 1\ $ずつ減らしながら見ていって、すべてうまくマッチングできるかを考えれば良い。$\ O(n ^ 2)\ $。

実装

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

#define all(x)  x.begin(), x.end()

int main() {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int i = 0; i < 2 * n; i ++) cin >> a[i];
        sort(all(a));
        map<int, int> cnt;
        for (int i = 0; i < 2 * n; i ++) cnt[a[i]] ++;
        set<int> x;
        for (int i = 0; i < 2 * n - 1; i ++) x.insert(a.back() - a[i]);
        for (auto X : x) {
                map<int, int> tmp = cnt;
                vector<int> ans;
                for (int i = 0; i < 2 * n; i ++) {
                        if (tmp[a[i]] == 0) continue;
                        tmp[a[i]] --;
                        if (tmp[a[i] + X] == 0) goto next;
                        tmp[a[i] + X] --;
                        ans.push_back(a[i] + X);
                }
                cout << X << endl;
                for (int i = 0; i < ans.size(); i ++) cout << ans[i] << (i == ans.size() - 1 ? '\n' : ' ');
                return 0;
                next:;
        }
        cout << -1 << endl;
        return 0;
}