全国統一プログラミング王 C問題：Different Strokes

問題. Different Strokes

$n$ 個の料理がある．A と B の二人が交互に料理を1つずつ選ぶ．A と B が $i$ 番目の料理を選んだときの幸福度をそれぞれ $a_i, b_i$ とする．お互いに自分のスコアである「自分が選んだ料理の幸福度の総和 - 相手が選んだ料理の幸福度の総和」を最大にするように選択する．このときの A のスコアを答えよ．

制約： $1 \le n \le 10^5$ ，　 $1 \le a_i, b_i \le 10^9$

解法

$N = \{1, 2, \ldots, n\}$ を料理の添字番号の集合とする．A と B が選んだ料理の添字番号の集合をそれぞれ $X, Y \subseteq N$ とする．このとき， $X, Y$ は $N$ の分割である．A と B のスコアはそれぞれ $\sum_{i \in X} a_i - \sum_{j \in Y} b_j$ と $\sum_{j \in Y} b_j - \sum_{i \in X} a_i$ でありこれをそれぞれが最大化するように選択する．ここで，B のスコアを変形すると $-(\sum_{i \in X} a_i - \sum_{j \in Y} b_j)$ と等しくなる．これは A のスコアを最小化することと同値である．よって， $S(X, Y) = \sum_{i \in X} a_i - \sum_{j \in Y} b_j$ とおくと，A と B はそれぞれ $S(X, Y)$ を最大と最小にするような分割 $X, Y$ を選ぶこととなる．
スコアをさらに同値変形をして，
　　 $S(X, Y) = \sum_{i \in X} (a_i + b_i) - \sum_{j \in N} b_j$
とする．このとき，後ろの和は定数なのでスコアは $X$ によって定まる．ここでスコアを $S(X, Y)$ の代わりに $S(X)$ で表す．A は $\sum_{i \in X} a_i + b_i$ の値が大きいものから選択することが最適となるので， $a_i + b_i$ の値で降順にソートして選ばれていないもので値が大きいものから選択していく．
B はスコア $S(X)$ を最小にするように料理を選択する必要があるが， $S(X)$ は A が選択する $X$ によって定まるのでB は $\sum_{i \in X} (a_i + b_i)$ が最小となるように A の選択を邪魔するように選ぶ．すなわち，A と同様に $(a_i + b_i)$ の値が大きいもので選ばれていないものから選択するのが最適選択となる（より詳細な証明はsmithの規則のように行う）．
以上から計算時間は $a_i + b_i$ の値を降順にソートする操作が支配的となるので $O(n \log n)$ 時間となる．

計算時間： $O(n \log n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;

    ll sum_b = 0;
    vector<ll> score(n);
    for (int i = 0; i < n; ++i) {
        ll a, b;
        cin >> a >> b;
        sum_b -= b;
        score[i] = a + b;
    }

    sort(score.begin(), score.end(), greater<ll>());
    ll sum_a = 0;
    for (int i = 0; i < n; i += 2)
        sum_a += score[i];

    cout << sum_a + sum_b << endl;

    return 0;
}

解けなかったので大いに反省．
目的関数が異なる場合はできるだけ同じになるように変形をすることを試みる（共通部分を探す）．

参考文献

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 解説