ARC164 C メモ

公式解説とは別の方針で解きました

問題

https://atcoder.jp/contests/arc164/tasks/arc164_c

問題文

$N$ 枚のカード、片面に $A_i$ 、もう片面に $B_i$ と書かれている。
はじめは全カード $A_i$ が表。
Alice と Bob が以下の手順をする。

Alice が残っているカードから 1 枚選び、裏返す。次に Bob が残っているカードから 1 枚選び、取り除く。表になっている数の得点を得る。

Alice は終了時の Bob の得点の最小化、Bob は得点最大化を目指す。
Bob が得ることのできる得点の最大値は？

制約

• $1 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^9$

サンプル

I/O 1

3
6 4
2 1
5 3

12

考察

赤青関係なく、その時点での表と裏を、それぞれ $A_i, B_i$ とする。
直感的に、 $A_i - B_i$ が大きいものを裏返す・取るのがベストだなーと思った。

というのも、

• Bob にとって $A_i - B_i$ を取るのが最適だとすると、 Alice は取られないように $A_i - B_i$ を裏返したほうがいい
• $i$ を裏返されると $A_i - B_i$ の得点が損になってしまうので、 Bob は裏返される前に早めにとっておきたい

(厳密な証明ができません、たすけて～)

よって、 $A_i - B_i$ を降順になるよう priority_queue で管理するようにして、実際に Alice と Bob の操作をシミュレーションする。
index の正負で赤・青のカードを管理するといい感じ。

コード

https://atcoder.jp/contests/arc164/submissions/43434481

int main() {
  int n;
  cin >> n;
  ll ans = 0;
  priority_queue<pair<ll, int>> q;
  vector<pair<ll, ll>> v(n);
  rep(i, n) {
    ll a, b;
    cin >> a >> b;
    v[i] = { a, b };
    q.push({ a - b, i + 1 });
  }
  rep(_, n) {
    // Alice
    auto [t, i] = q.top();
    q.pop();
    q.push({ -t, -i });
    // Bob
    auto [s, idx] = q.top();
    q.pop();
    if (idx > 0) {
      ans += v[idx - 1].first;
    }
    else {
      ans += v[-idx - 1].second;
    }
  }
  cout << ans << endl;
  return 0;
}