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; }