CADDI_2018_B / CADDI_2018B_D - Harlequin

[zeikar]

Problem link

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b

Problem Summary

플레이어와 Lunlun이 번갈아 가며 게임을 한다.
한 턴에 다른 색의 사과만을 먹을 수 있다.
마지막 사과를 먹은 사람이 승자일 때 승자를 구하는 문제.

Solution

이런 게임류 문제가 생각보다 까다롭다.

일단, 예제 1번에서 얻을 수 있는 정보는 사과가 한 종류만 남았을 경우 짝수개이면 무조건 진다는 것이다. (하나씩밖에 못 가져가므로)
사과가 두 종류일 때를 시뮬레이션 해보자.
2, 2인 경우 첫 번째 플레이어가 한 종류만 먹는다고 하면 1,2 이고 두 번째 플레이어가 1개 남은 사과를 먹게 되면 두 번째가 승리한다.
만약 첫 번째 플레이어가 두 종류 다 먹는다면 1,1이 되고 이렇게 해도 두 번째 플레이어가 둘 다 먹게 되어 두 번째가 승리한다.

짝수개로 일반화도 가능한데, 2n, 2n개인 경우 첫 번째 플레이어가 둘 다 먹든 하나만 먹든 다른 플레이어가 남은 사과의 수를 짝수로 만들어 버릴 수 있으므로 이길 수 없다.

에디토리얼을 참고하면 모든 사과가 짝수인 상태를 E, 하나라도 홀수가 있다면 O 로 정의한다. 마지막 승리 상태도 E로 볼 수 있다.
처음 시작이 E인 상태일 때 첫 번째 플레이어가 뭘 하든 O 상태로 변화되고 두 번째 플레이어는 다시 E로 전환시킬 수 있다.
처음 시작이 O인 상태일 때는 첫 번째 플레이어가 E로 변환시킬 수 있다.

즉, 처음 시작이 E인 경우 두 번째 플레이어가 이기고 처음 시작이 O인 경우는 첫 번째 플레이어가 이기게 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int a[100000];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	string ans = "second";
	for (int i = 0; i < n; i++)
	{
		if (a[i] % 2 != 0)
		{
			ans = "first";
			break;
		}
	}

	cout << ans << endl;
}