mayoko’s diary

プロコンとかいろいろ。

Educational Codeforces Round 6 D. Professor GukiZ and Two Arrays

解法

まず 0 回交換の場合, 1 回交換の場合はそのまま O(nm) で調べることが出来ます。

で, 2 回交換の場合は, a から b に渡すことの出来る 2 つの数の和のリストおよび b から a に渡すことの出来る 2 つの数の和のリストを O(n^2log n + m^2 log m) で作ります。

a から x だけ b に移して b から y だけ a に移すと, a, b の配列の和の差は,
(sumA - x + y) - (sumB - y + x) = (sumA-sumB) + 2*(y-x) となります。この値を diff とすると,
y = x + (sumB-sumA)/2 + diff/2 となります。diff はだいたい 0 であるのが嬉しいので, y の値について lower_bound を取って, その周辺を適当に調べれば答えが得られます。
コード中の index の±1 を調べれば良いかなと思ったんですがなんか WA したので ±10 調べました。

const int MAX = 2020;
const ll INF = 1ll<<55;
int a[MAX], b[MAX];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++) cin >> b[i];
    ll suma = 0, sumb = 0;
    for (int i = 0; i < n; i++) suma += a[i];
    for (int i = 0; i < m; i++) sumb += b[i];
    ll bestV = abs(suma-sumb);
    vector<pii> best;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ll sa = suma-a[i]+b[j];
            ll sb = sumb-b[j]+a[i];
            if (bestV > abs(sa-sb)) {
                bestV = abs(sa-sb);
                best.clear();
                best.emplace_back(i, j);
            }
        }
    }
    vector<pair<ll, pii> > va, vb;
    for (int i = 0; i < n; i++) for (int j = i+1; j < n; j++) {
        va.emplace_back(a[i]+a[j], pii(i, j));
    }
    for (int i = 0; i < m; i++) for (int j = i+1; j < m; j++) {
        vb.emplace_back(b[i]+b[j], pii(i, j));
    }
    sort(va.begin(), va.end());
    sort(vb.begin(), vb.end());
    if (!vb.empty()) {
        for (auto p : va) {
            ll x = p.first;
            pair<ll, pii> tmp(x+(sumb-suma)/2, pii(-1, -1));
            int index = lower_bound(vb.begin(), vb.end(), tmp) - vb.begin();
            for (int i = max(index-10, 0); i < min<int>(index+10, vb.size()); i++) {
                ll y = vb[i].first;
                ll sa = suma-x+y, sb = sumb-y+x;
                if (bestV > abs(sa-sb)) {
                    bestV = abs(sa-sb);
                    best.clear();
                    best.emplace_back(p.second.first, vb[i].second.first);
                    best.emplace_back(p.second.second, vb[i].second.second);
                }
            }
        }
    }
    cout << bestV << endl;
    cout << best.size() << endl;
    for (pii p : best) cout << p.first+1 << " " << p.second+1 << endl;
    return 0;
}