NIKKEI Programming Contest 2019 C - Different Strokes

概要

項の数列とが与えられ、二人でゲームを行う。
先手が数字iを選ぶと全体の得点に加算され、後手が数字iを選ぶと全体の得点から減算される。
先手は全体の得点を最大化、後手は全体の得点を最小化させたい。
二人が最適に行動するとき、全体の得点の最大値を求めよ。

制約

方針

先手・後手ともにが大きい順にとっていく。

感想

本番はちょっとどつぼにはまった感じ。
順位表見ると早めに解けている人が多かったので、シンプルな戦略を考えていたら思いついたかもしれない。

解答

Submission #4111131 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
#define fi first
#define se second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> A(N);
	vector<ll> B(N);
	rep(i, N) cin >> A[i] >> B[i];
 
	vector<pli> v(N);
	rep(i, N) v[i] = (pli){A[i] + B[i], i};
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
 
	ll ans = 0;
	rep(i, N){
		if(i % 2 == 0){
			ans += A[v[i].se];
		}else{
			ans -= B[v[i].se];
		}
	}
 
	cout << ans << endl;
}