Card Groups [CSAcademy #60 D]

https://csacademy.com/contest/round-60/task/card-groups/

N枚のカードがある。
i番目のカードは赤面にA[i], 青面にB[i]が書かれている。
N枚のカードをそれぞれ赤・青にした時に、赤の数の合計と青の数の合計を同じにしたい。
もし幾つか、組合せがある場合には、赤の枚数と青の枚数の差を最小化して実現したい。
どのように選べばいいかを文字列Sで出力せよ。
S[i] := i番目のカードが赤なら'0', 青なら'1'
実現不可能なら"-1"

前提知識

• 半分全列挙

解法

半分全列挙する。
2グループに分け（グループA,Bとしておく）、solve(v)をする。
solve(v) := カードの集合vについて(赤の数の合計-青の数の合計, 赤の枚数-青の枚数)を全列挙する
「赤の数の合計-青の数の合計」としておくことで合計が0になるものを考えればよくなる。
全列挙した後、昇順ソートしておこう。
　
次にグループAに含まれる全列挙された組について全探索を行う。
グループAの「赤の数の合計-青の数の合計」をp.first
グループAの「赤の枚数-青の枚数」をp.second
として考える。
グループBからも全探索で最適なやつをとってくると普通の全列挙でTLEなので、効率よく取ってくることを考える。
グループBの中から取ってきたい最適なペアは(-p.first, -p.second)である。
これをlower_boundで取ってこよう。
もし最適なペアが無くてもそこそこ最適なやつが見つかるので、一応indexが±1の所を探索して最適な答えを見つけてこよう。
　
最後にどのように選択したかを復元する必要があるので、グループA,Bについて合計の差と枚数の差をメモしておきget関数で復元する。

typedef long long ll;
using T = pair<ll, int>;
int N; ll A[50], B[50];
//---------------------------------------------------------------------------------------------------
vector<T> solve(vector<int>& v) {
    int n = v.size();
    vector<T> res;
    rep(msk, 0, 1 << n) {
        ll sm = 0;
        int cnt = 0;
        rep(i, 0, n) {
            if (msk & (1 << i)) sm += A[v[i]], cnt++;
            else sm -= B[v[i]], cnt--;
        }
        res.push_back({ sm, cnt });
    }
    sort(res.begin(), res.end());
    return res;
}
//---------------------------------------------------------------------------------------------------
string get(vector<int>& v, ll gsm, int gcnt) {
    int n = v.size();
    vector<T> res;
    rep(msk, 0, 1 << n) {
        ll sm = 0;
        int cnt = 0;
        rep(i, 0, n) {
            if (msk & (1 << i)) sm += A[v[i]], cnt++;
            else sm -= B[v[i]], cnt--;
        }
        if (sm == gsm and cnt == gcnt) {
            string res = "";
            rep(i, 0, n) {
                if (msk & (1 << i)) res += "0";
                else res += "1";
            }
            return res;
        }
    }
    assert(0);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];
    vector<int> v[2];
    vector<T> w[2];
    rep(i, 0, N) v[i % 2].push_back(i);
    rep(i, 0, 2) w[i] = solve(v[i]);

    int dlt = 1010;
    ll smA = 0, smB = 0;
    int cntA = 0, cntB = 0;
    int m = w[1].size();
    fore(p, w[0]) {
        int i = lower_bound(w[1].begin(), w[1].end(), make_pair(-p.first, -p.second)) - w[1].begin();

        if (i < m) if (p.first + w[1][i].first == 0) {
            if (abs(p.second + w[1][i].second) < dlt) {
                dlt = abs(p.second + w[1][i].second);
                smA = p.first;
                smB = w[1][i].first;
                cntA = p.second;
                cntB = w[1][i].second;
            }
        }

        if (i + 1 < m) if (p.first + w[1][i + 1].first == 0) {
            if (abs(p.second + w[1][i + 1].second) < dlt) {
                dlt = abs(p.second + w[1][i + 1].second);
                smA = p.first;
                smB = w[1][i + 1].first;
                cntA = p.second;
                cntB = w[1][i + 1].second;
            }
        }

        if(i) if (p.first + w[1][i - 1].first == 0) {
            if (abs(p.second + w[1][i - 1].second) < dlt) {
                dlt = abs(p.second + w[1][i - 1].second);
                smA = p.first;
                smB = w[1][i - 1].first;
                cntA = p.second;
                cntB = w[1][i - 1].second;
            }
        }
    }

    if (dlt == 1010) {
        printf("-1\n");
        return;
    }

    string s[2];
    s[0] = get(v[0], smA, cntA);
    s[1] = get(v[1], smB, cntB);

    string ans = "";
    rep(i, 0, N) ans += s[i % 2][i / 2];
    cout << ans << endl;
}