PS 일지(2021.11.04)

14555. Just as Tic Tac Toe

Diamond 4

문제 분석

문제는 N개의 바구니에서 3개의 바구니를 선택했을 때, 리샤가 승리하는 조합의 수를 출력하는 문제였다.
기본적으로는 스프라그 그런디 정리를 사용하는 문제처럼 보이나, N이 50만이라서 어떤 방식으로든 최적화가 필요한 문제였다.

풀이

우선 주어진 입력을 모두 $(M+1)$로 나눈다. 그 후 $a\oplus b=c$를 만족하는 가짓수를 모두 세면 된다.
가장 naive한 방식은 $O(N^3)$의 풀이가 될 것이다. $(a,b,c)$를 한 쌍씩 모두 구해 셋의 xor이 0인 개수를 세면 될 것이다.

이걸 그나마 최적화를 한다고 하면, 빈도수 배열을 만들어 저장한 뒤, $(a,b)$의 쌍만 구해 c와 비교하는 식의 풀이가 될 것이다. 이는 $O(N^2)$이 될 것이다.

앞에서 말했듯, N은 50만이어서 이런 풀이가 택도 없다.

여기서 FFT를 대입을 해보자.
기본적으로 두 집합의 xor set을 구하는 경우는 결국 $Z_2*Z_2* \cdots Z_2$ 끼리의 곱으로 생각할 수 있고, 이를 수행해주는 알고리즘이 바로 FWHT(Fast Walsh Hadamard Transform)이다.

이에 관한 정리는 Fast Walsh Hadamard Transforms 여기에 내가 할 수 있는 최대한 자세히 정리해뒀다.

이게 끝이다. 두 집합의 xor set을 구하고 원래 배열과 중복없이 모든 순서쌍을 세기만 하면 되는 문제이다.

고찰

이 문제는 어쩌다 게임이론 문제들을 풀다보니 만나게 된 문제지만, 정말 많이 배울 수 있었다.
앞으로 게임이론 문제 셋을 모두 밀 예정인데, 이런 방식의 PS가 생각보다 도움이 많이 되는 것 같다.

풀고 있는 알고리즘 리스트(Platinum V 이상)

• 게임 이론 (34/104)