4bitにっき

ぽよ

Game Theory (HackerRank) : Fun Game

貪欲

問題

Programming Problems and Competitions :: HackerRank
サイズがnの数列A, Bがある。
2人のプレイヤーはそれぞれのターンで以下の操作を行う。
・0 <= i <= n-1 となるiを1つ選ぶ。
・プレイヤー1ならA[i]点、プレイヤー1ならB[i]点を得る。
・ゲーム全体で、同じiを2回選ぶことは出来ない。
最後に、点数の総和が大きい方が勝ち。
勝つのはどちらか。

解法

自分の点数をなるべく大きくすることも敵の点数を小さくすることも同じだけ重要っぽいので、iをA[i]+B[i]の降順ソートして各プレイヤーが手前のものから使っていく貪欲を行う。
直感的にはうまくいきそうだが、厳密な証明方法が分からない。(誰か教えて下さい...)

追記(証明)

(バタ子@btk15049さんとDiv@Div9851君から方針を教えてもらいました。ありがとうございます。)

C = {A[0]+B[0], ... , A[n-1]+B[n-1]} と置いて、2人のプレイヤーが交互にこの数列の要素を取り合い、取った要素の総和(Q1, Q2とする)で競うゲームを考える。
このゲームの最適解は明らかに大きいものから取ることである。

元のゲームの各プレイヤーの点数をP1, P2、このゲームで各プレイヤーの選んだインデックスの集合をS1, S2とすると、(Q1-Q2)は以下のように変形できる。
(見づらいので拡大推奨)
\large Q1 - Q2 \\
\Large = \sum_{j \in S1}C_{j} - \sum_{j \in S2}C_{j} \\
\Large = \sum_{j \in S1}(A_{j} + B_{j}) - \sum_{j \in S2}(A_{j} + B_{j}) \\
\Large = \{ \sum_{j \in S1}A_{j} + (\sum_{}B - \sum_{j \in S2}B_{j}) \} \\ \Large \hspace{4em} - \{ \sum_{j \in S2}A_{j} + (\sum_{}A - \sum_{j \in S1}A_{j}) \}
\Large = (\sum_{}B - \sum_{}A) + (2\sum_{j \in S1}A_{j} - 2\sum_{j \in S2}A_{j})
\Large = (\sum_{}B - \sum_{}A) + 2(P1 - P2)
式の左部分は定数だから、例えばプレイヤー1が元のゲームで(P1-P2)を最大化しようと思うと(Q1-Q2)を最大化すればよいことになる。
つまり、このゲームの戦術は元のゲームにそのまま適用できて、元のゲームでもA[i]+B[i]の大きい順に貪欲に取ればよいことが分かる。

実装

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_N = 1000;

struct Point
{
	int a, b;
	Point() : a(0), b(0) {}
	bool operator < (const Point &p) const
	{
		return a + b > p.a + p.b;
	}
};

int T, N;
Point p[MAX_N];

signed main()
{
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			cin >> p[i].a;
		}
		for (int i = 0; i < N; i++)
		{
			cin >> p[i].b;
		}
		sort(p, p + N);
		int a = 0, b = 0;
		for (int i = 0; i < N; i++)
		{
			if (i&1) b += p[i].b;
			else a += p[i].a;
		}
		if (a > b) puts("First");
		else if (a < b) puts("Second");
		else puts("Tie");
	}
	return 0;
}