Asa's Website

C - Reversible Card Game

cpatcodergreedydiff green

最終更新日

Table of Contents

Loading...

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

問題

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

問題文

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

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

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

制約

サンプル

I/O 1

3 6 4 2 1 5 3
12

考察

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

というのも、

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

よって、 AiBiA_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; }