14705 홍삼 게임 (Hard)

문제

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

개요

매우 단순화하면 게임은 다음 프로세스의 반복이다.

1. 지목권 A 가진 사람이 A 양도
2. 지목권 B 가진 사람이 B 양도

분석1

n번째에 A 지목권이 오간다면 n+2번째에 다시 A 지목권이 오간다. 이는 B 지목권에도 동일하게 적용된다.

n번째에 어떤 지목권으로 지목했다면 n + 4k(k >= 0인 정수)에 같은 사람이 같은 지목권으로 지목받을 수 있다.

• 얍샙이 플레이를 하는 두 사람(x, y)이 있다. x가 n번째에 어떤 지목권으로 y를 지목했을 때 y가 n+2번째에 x를 같은 지목권으로 지목할 수 있다. x는 다시 n + 4번째 지목에 같은 지목권으로 y를 지목 가능하다.
• 즉 x는 n + 4k(k >= 0인 정수)번째 지목에 같은 지목권을 다시 사용할 수 있다. 여기서 n이 x가 A를 가질 수 있는 최소의 지목 횟수라고하면 n + 4k는 x가 지목할 수 있는 모든 지목횟수를 포함할 수 있다.

결론

따라서 1번째 부터 N번째 사람이 최소 몇번째 지목에 선택될 수 있는지 알아야한다.

• A로 인해 지목됐는지, B로 인해 지목됐는지 구분해야한다.
• n + 4k 번째 지목에 같은 지목권을 다시 사용할 수 있으므로 나머지가 0,1,2,3인 최소 지목횟수를 구해야한다. 왜냐하면 n + r1 + 4k 와 n + r2 + 4k 는 겹치지 않기 때문이다. (0 <= r1,r2 <= 3, r1 != r2)
  • (여기서 어떤 지목권을 가지느냐에 따라 지목 횟수 나머지는 (0,2),(1,3) 둘 중 한 묶음에만 해당된다. (n + 2)번째에 같은 지목권이 오가기 때문이다. 편하다면 케이스처리를 해도 되지만 난 케이스처리를 안하는게 코드가 깔끔했다.)

# 각 지목권 별 최소 지목 횟수
DA = [[INF] * N for _ in range(4)]  # DA[r][x]: 최소 지목 횟수 x=사람번호, r=지목횟수%4
DB = [[INF] * N for _ in range(4)]
DA[0][A] = 0
DB[1][B] = 1
aq = deque([(A, 0)]) # A 지목권 최소 횟수 구하기 위한 큐
bq = deque([(B, 1)]) # B 지목권 최소 횟수 구하기 위한 큐
# 참고로, 문제의 의도상 초기값은 -1과 0으로 해야한다. 하지만 난 최종값에서 1을 빼주는 것을 선택했다.
# 이 코드상 은하가 먼저 지목권 A를 나눠준 사람이 지목하는 순서는 2가되는 점을 유의하라(문제의 의도는 순서 1)


def fill():
    def get(n, d): # 지목권을 양도할 왼쪽, 오른쪽 사람을 구함
        return [(n - d + N) % N, (n + d) % N]

    while aq or bq:
        if aq:
            n1, c1 = aq.popleft() # 사람, 지목횟수
            for n in get(n1, X):
                c = c1 + 2 # 다음 같은 지목권은 + 2
                if c < DA[c % 4][n]: # 최소값 갱신
                    DA[c % 4][n] = c
                    aq.append((n, c))
        if bq:
            n2, c2 = bq.popleft()
            for n in get(n2, Y):
                c = c2 + 2
                if c < DB[c % 4][n]:
                    DB[c % 4][n] = c
                    bq.append((n, c))

분석2

게임이 끝나는 경우는 두가지가 존재한다

1. A를 양도했는데 B를 이미 가지고 있던 경우
2. B를 양도했는데 A를 이미 가지고 있던 경우

두 케이스별로 DA와 DB를 해석해야한다.

값을 초기화를 어떻게 하냐에 따라 달라진다. 게시자처럼 초기화한다면 1을 빼줘야한다.

1. max(DA[r][i]-1, DB[(r-1+4)%4][i]): A를 양도했는데 이전 순서에 같은 사람이 B를 가졌다.
2. max(DB[r][i]-1, DA[(r-1+4)%4][i]): B를 양도했는데 이전 순서에 같은 사람이 A를 가졌다.