[Python] 29154번 작곡가 A의 시창 평가

https://www.acmicpc.net/problem/29154

---

 

24/05/16

 

 

이전에 해결했었던 스그 문제인데, 꾸역꾸역 kmp랑 엮어서 만들었다는 느낌을 너무 강하게 받은 문제이다.

---

 

문제 접근 방식:

 

 

일단 선/후공 승패 여부 판단하고, 색칠된 부분이 여러 개의 모습으로 분리되며, 색칠된 부분을 그냥 님게임으로 간주할 수 있다는 사실은 스프라그 그런디 정리를 많이 풀어본 사람이라면 쉽게 파악할 수 있을 것이다.

 

문제는 그러면 색칠된 부분을 어떻게 빠르게 구할건데?가 핵심이 된다.

 

보면 멜로디 $L$과 멜로디 $L$의 접미사들을 "모두" 기존 문자열 $S$에서 찾아야 한다.(빠르게)

 

그러면 당연히 생각나는건? kmp다.

 

kmp의 동작 원리를 생각하면 접두사와 접미사가 일치하는 부분을 통해 "당겨옴"으로써 빠르게 문자열을 찾는거고, 멜로디 $L$의 접미사들을 모두 기존 문자열에서도 찾아야 하므로, 그냥 kmp한번 스근하게 돌리면 충분하다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 29154번 작곡가 A의 시창 평가
# KMP, 스프라그-그런디 정리
'''
접근 방법:
악보가 S, 멜로디를 L이라고 한다.
그러면 악보와 멜로디를 모두 뒤집는다.
이후 KMP를 돌린다.
한 번의 KMP만으로 가능하다.
이후 쪼개진 문자열의 길이를 다 구하고 스그 정리 적용.
'''
import sys
input = sys.stdin.readline
from functools import reduce
def compute_pi_array(W):
    M = len(W)
    fail = [0 for _ in range(M)]
    j = 0
    for i in range(1, M):
        while W[i] != W[j] and j > 0:
            j = fail[j-1]
        if W[i] == W[j]:
            j += 1
            fail[i] = j
    return fail
def KMP(S, W, fail):
    N, M = len(S), len(W)
    j = 0
    result = []
    for i in range(N):
        while S[i] != W[j] and j > 0:
            j = fail[j-1]
        if S[i] == W[j]:
            result.append(i)
            if j == M-1:
                j = fail[j]
            else:
                j += 1
    if result == []:
        return [0]
    stone = 1
    stones = []
    for i in range(1, len(result)):
        if result[i] - result[i-1] == 1:
            stone += 1
        else:
            stones.append(stone)
            stone = 1
    stones.append(stone)
    return stones
N, M = map(int, input().split())
S = list(reversed(list(map(int, input().split()))))
M = list(reversed(list(map(int, input().split()))))
ans = reduce(lambda x, y: x^y, KMP(S, M, compute_pi_array(M)))
print('First' if ans else 'Second')