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