BOJ 30514 두근 어질

문제 링크입니다.

제가 SASA Programming Contest 2023에 출제한 문제입니다.

원래는 Smaller-to-Larger 테크닉을 사용하는 $\mathcal{O}(N \log^2 N)$ 풀이를 의도한 문제인데, 더 좋은 풀이가 있었습니다.

관찰

서로 다른 두 종류 이상의 꽃이 있는 꽃집이 없는 날들에 한해서, 세종이와 아름이는 해야 하는 행동이 모두 결정되어 있는 상태입니다.

첫 전략 세우기

처음으로 2종류의 꽃이 있는 꽃집이 생기는 날을 생각해 봅시다. 그때의 꽃집은 하나는 꽃이 2종류, 나머지는 1종류인 상황이 됩니다. 이때 먼저 꽃을 가져가는 사람이 꽃이 2종류인 꽃집에서 1종류나 2종류의 꽃을 가져가면, 그에 따라 이번 게임의 승패가 결정됩니다. 따라서 이때의 선공은 다음 게임에서 선공을 할지 혹은 후공을 할지 결정할 수 있습니다.

이후 게임의 결과 생각해보기

체르멜로 정리라는 게 있는데요. 무승부 없는 2인 유한 완전 정보 게임에는 선공이나 후공 중 한 쪽에 반드시 필승 전략이 존재한다는 내용입니다. 이 게임은 체르멜로 정리를 만족시키기 때문에, 게임의 중간 과정 중 어떤 지점을 잡아도 그때 선공이나 후공 중 한 쪽에 필승 전략이 있습니다.

그런데 아까 처음으로 꽃의 종류가 2가지인 꽃집이 생겼을 때 선공이 다음 게임에서의 선후공을 결정할 수 있다는 걸 알아냈습니다. 다음 게임에서의 선공이나 후공 중 한쪽에게는 필승 전략이 있으므로, 지금 선공은 다음 게임에서 필승 전략이 있는 쪽이 되도록 이번 게임의 결과를 결정할 수 있습니다. 따라서, 이때의 선공이 최적의 전략을 사용하면 전체 게임에서 승리하고 고백을 할 수 있습니다.

결국 문제는 처음으로 2종류의 꽃이 있는 꽃집이 생길 때까지 기계적으로 움직이는 세종이와 아름이를 시뮬레이션하는 것으로 해결할 수 있고, 이는 각 날마다 $\mathcal{O}(1)$에 가능합니다.

총 시간복잡도는 $\mathcal{O}(N)$입니다.

코드

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

int a[101010];

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i];
	int ans = n&1;
	for(int i = 0; i < n-1; i++){
		int u, v; cin >> u >> v;
		if(a[u] != a[v]) break;
		ans ^= (n-i)&1;
	}
	cout << (ans?"Sejong":"Areum");
}