Different Strokes - AtCoder 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 C

400点
問題リンク

考察の流れ

　2人分の得点について考えるのは面倒なので、得点を1種類のみにしてやりたいです。最終的に出力するのは「高橋くんの点数 - 青木さんの点数」なので、この点数についてずっと考えてやると良さそうです。

　こういう問題は、僕の場合はまず高橋くんの料理の選び方から考えていきます。
　高橋くんが料理を選ぶと何が起こるでしょうか。高橋くんは点得ますが、同時に青木さんは点を失うというふうに考えてみます。高橋くんは、が大きい料理から順にとっていくと良さそうな気がします。高橋くんが料理を選ぶと、高橋くんと青木さんの点数の差は大きくなるというわけです。すると、青木さんが料理を選ぶルールも同様で、この点数が大きい順にとっていきます。こうすることで、aとbの2種類あった点数が1種類に収まりました。
　このように考えるならば、初めは青木さんが全ての料理を持っていて、それから1ターンおきに高橋くんが料理を奪っていく、というふうに考えるとよさそうです。高橋くんはが大きい料理から順にとっていきますが、同時に青木さんも同じルールで自分の料理を選んでいくので、高橋くんは実際には奇数番目にが大きい料理を選ぶことができます。
　
　もちろん逆でも構いません。高橋くんが全ての料理を独り占めしていて、それを青木さんが奪っていくタイプのプログラムでもいいと思います。僕はこちらでやりました。

▶ソースコードを開く

int n;
int a[100005], b[100005];
int score[100005];
int sum;

signed main(){
	scanf("%ld", &n);
	for(int i = 0; i < n; i++){
		scanf("%ld %ld", &a[i], &b[i]);
		score[i] = a[i] + b[i];
		sum += a[i];
	}
	std::sort(score, score+n, std::greater<int>());
	for(int i = 0; i < n; i++){
		if(i % 2 == 1){
			sum -= score[i];
		}
	}
	printf("%ld\n", sum);
	return 0;
}