4bitにっき

ぽよ

Game Theory (HackerRank) : Misère Nim

Nim

問題

Programming Problems and Competitions :: HackerRank
Nimゲームとほぼ同じだが、最後の石を取ったほうが負け(動かせなくなった方の勝ち)であるところが違う。

解法

Nim - sigma425のブログ
↑より分かりやすそうな説明

(1, 1, 1, ...)

まず、 s_{i} = 1の山だけしかなくて、それが奇数個の場合、これは負けの状態である。逆に偶数個なら勝ちの状態である。

(2, 1, 1, ...)

次に s_{i} > 1である山が1つだけあり、残りが全くないか s_{i}=1だとする。 s_{i} > 1である山を崩して s_{i} = 1である山の遇奇を自由にいじれるので、これは勝ちの状態である。
普通にゲームをしていればこの状態は避けられないので、この状態で手番が回ってきた方の勝ちだと分かる。


上のような状態を奪うにはどうすればいいだろうか。
普通のNimと同じような戦法を取ってみる。
XOR(s_{1}, ... , s_{n}) > 0の状態で回ってきた方が、常にXOR=0の状態を相手に渡し続けていく。
上で説明した 2, 1, 1, ... のような状態はXOR>0だから、XOR>0で回ってきたプレイヤーはこの状態を奪えるので、ここでNim戦法をやめて遇奇をいじれば勝てる。

全ての山が最初から1の時だけ勝敗条件が変わることに気をつけなければいけない。

実装

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

#define int long long

int T, N, S[100];

signed main()
{
	cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
		cin >> N;
		int ma = 0, x = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> S[i];
			x ^= S[i];
			ma = max(ma, S[i]);
		}
		if (ma < 2) puts((N&1) ? "Second" : "First");
		else puts(x ? "First" : "Second");
	}
	return 0;
}