[ARC164] C - Reversible Card Game

[Q] https://atcoder.jp/contests/arc164/tasks/arc164_c

考察
・大きい数字が出ているカードを「裏返し」と考える。
・シミュレーションすると、Bobがかなり有利っぽい。
・Bobは次の2パターンしかなさそう。
1. 全部のカードの最大値をとれる
2. 1ペアだけ最大をとれない
取れないときはどんなとき？
・場の全カードが低い値になってしまった場合、1ペアだけBobは低い値を取らざるを得ない。その後の展開はAliceが裏返したものをBobが選び続けるので、大きい値をとり続けられる。

低い1ペアをとらされるのはどんなとき？
大きい数字が出ているカードを「裏返し」と考えると。
1. Alice行動前に裏返しのカードが偶数のとき、Bobは全部のカードの最大値をとれる。
Aliceがひっくり返すと、奇数枚のカードが裏返しになるから、必ずBobは大きい値をとれる。
2. Alice行動前に裏返しのカードが奇数のとき、Bobは1枚だけ低い値をとらされるようだ。
いずれ1枚だけ裏返っている状況になり、Aliceが全部表にしてしまう。
低い値は何を取らされる？
・Aliceがどうがんばっても、Bobは最もロストの低いカードを選ぶことができるようだ。abs(B - A)が最も小さいカードを選べばいい。

実装

int main() {
  cincout();
  
  ll N;
  cin >> N;
  
  vector<ll> A(N), B(N);
  ll ans = 0;
  ll bigA = 0;
  ll minDif = oo;
  rep(i, N){
    cin >> A[i] >> B[i];
    ans += max(A[i], B[i]);
    if (A[i] > B[i]) ++bigA;
    chmin(minDif, abs(A[i] - B[i]));
  }
  if (bigA % 2 == 0){ // 全部大きい値をとれる
    cout << ans << endl;
    return 0;
  }
  // 1枚だけ、損が少ないカードをとる
  ans -= minDif;
  cout << ans << endl;
}

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