[Python] 31541번 1차원 돌 게임 1 (추후 보강 예정)

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

---

 

25/07/03

 

 

플레티넘 200문제를 채우기 위해 풀었던 문제 중 하나이다. 규칙을 찾아서 해결했다.

---

 

문제 접근 방식:

 

 

일단 $T$의 제한이 $10^6$으로 수상하게 크고, $n$의 제한 또한 $10^{18}$으로 크므로, $\mathcal{O}(1)$에 준하는 시간으로 답이 나와야 함을 추측할 수 있다.

 

 

게임 이론 문제이고, 서브태스크가 각 제한 별로 나와있어서, 주어진 작은 제한 $n = 1000$까지에서 DP를 돌려 규칙을 찾아보기로 했다.

 

상태 식은 다음과 같이 정의된다.

 

$$DP[N][K] = N개의 돌이 있고, 현재 K개의 돌을 가져가야 할 경우의 승패 여부$$

 

당연히 $N < K$라면 가져갈 수 있는 상황이 아니므로, 선공이 지게 된다. 즉, $0$이다.

 

$N == K$라면 선공이 딱 맞춰서 다 가져가면 되므로, 선공이 이기게 된다. 즉, $1$이 된다.

 

그 외의 경우라면, 연속된 $K$개의 돌을 가져가야 한다. 나머지 연속된 돌더미들 중 작은 돌더미는 버리고, 다음 차례의 상대는 $K+1$개의 돌을 가져가야 하므로, 아래의 값들을 참조해야 한다.

 

$$DP[N-K][K+1], DP[N-K-1][K+1], \dots$$

 

가운데 $K$개를 가져갔다면, 이를 기준으로 왼쪽으로는 $i$개, 오른쪽으로는 $N-K-i$개의 연속한 돌이 남게 되는데, 둘 중 더 긴 연속한 돌만 남게 되므로, $\max (N-K-i, i)$개의 이전 DP값을 참조하게 된다.

 

참조하는 DP값들이 모두 선공이 이기는 상황이라면, 내가 차례를 넘겨줄 때 선공이 이기도록(즉, 내가 후공이 되고 상대방이 선공이 되는데, 상대방이 이기도록) 넘겨줄 수 밖에 없으므로 현재 DP값은 $0$이 된다.

 

그 외의 경우는 $1$이 될 것이다.

 

 

이렇게 나이브하게 $\mathcal{O}(N^2)$ DP풀이를 짜고, $DP[n][1]$들을 모두 모아 $1000$개의 값들을 조회해보았다.

 

$0$과 $1$이 번갈아가며 연속하게 있었는데, 그 연속된 개수의 숫자가 일정한 규칙을 띄고 있는 것 같았다.

 

일단 연속한 $0$과 $1$이 서로 바뀌는 지점을 찍어보았다.

 

0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
0 3 7 23 33 87 109 263 309 711 805

 

위의 줄은 DP값들을 $20$개까지 찍은 것이고, 밑의 줄은 $0$과 $1$이 서로 바뀌기 직전의 인덱스를 출력한 것이다.

 

이때, 위의 인덱스를 통해 연속한 $0$의 개수와 $1$의 개수를 구할 수 있었다.

 

이는 다음과 같다.

 

1 4 10 22 46 94
3 16 54 154 402

 

위는 연속한 $0$의 개수이고, 아래는 연속한 $1$의 개수이다.

 

연속한 $0$의 개수를 보면 이전 항에 $2$를 곱하고 $2$를 더하면 다음 항이 나옴을 확인할 수 있었다.

 

즉, 연속한 $0$의 개수에 대한 일반항은 $3\cdot 2^n  - 2$라고 추측할 수 있었다.

 

 

이후 연속한 $1$의 개수에 대한 규칙을 발견하기가 꽤나 어려웠다.

 

$0$과 $1$이 바뀐 직후의 인덱스를 출력하고 규칙을 발견할 수 있었다.

 

$$1 \ \ 4 \ \ 8 \ \ 24 \ \ 34 \ \ 88 \ \ 110 \ \ 264 \ \ 310 \ \ 712 \ \ 806$$

 

$4$에서 $8$로 넘어갈 때는 연속한 $0$의 개수($4$개)만큼 더해진다. 이후 $24$라는 인덱스는 (연속한 $0$의 개수) + $8$의 $2$배이다.

 

마찬가지로, $24$에서 $34$로 넘어갈 때에는 연속한 $0$의 개수($10$개)만큼 더해진다. 이후 $88$이라는 인덱스는 (연속한 $0$의 개수) + $34$의 $2$배이다.

 

$88$에서 $110$넘어갈 때에도 연속한 $0$의 개수($22$개)만큼 더해지고, 이후 $264$라는 인덱스는 (연속한 $0$의 개수($22$)) + $110$의 $2$배가 된다.

 

 

이전에 연속한 $0$의 개수에 대한 일반항을 미리 구해놨고, 이를 통해 $0$과 $1$이 바뀐 직후의 인덱스를 모두 전처리로 찾을 수 있었다.

 

해당 리스트를 통해 승/패 여부를 빠르게 판단할 수 있었다.

 

실제로 잘 동작해서 AC를 받았지만, 어째서 이런 동작이 나왔고 해당 규칙이 왜 정당화 되는지에 대한 증명을 하지 못했다.

 

만약 해당 부분을 알게된다면 보충해서 작성할 계획이다.

---

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

# 31541 1차원 돌 게임 1
# 게임이론
'''
접근 방법:
규칙을 찾아보자
DP[N][K] = N개의 돌이 있는데 현재 K개의 돌을 가져가야 할 경우 승패
N < K -> 0
N == K -> 1
DP[N][K] ->
DP[N-K][K+1], DP[N-K-1][K+1], ...
max(N-K-i, i)
'''
import sys
input = sys.stdin.readline
'''
W = 1001

DP = [[0 for _ in range(W)] for _ in range(W)]
for n in range(1, W):
    DP[n][n] = 1
    for k in range(1, n):
        for i in range(n):
            if n-k-i < i: break
            if DP[n-k-i][k+1] == 0:
                DP[n][k] = 1
                break
ans = [DP[n][1] for n in range(W)]
change = []
for i in range(W-1):
    if ans[i] != ans[i+1]:
        change.append(i)
zero = [1]
for i in range(1, len(change), 2):
    zero.append(change[i+1]-change[i])
one = []
for i in range(0, len(change)-1, 2):
    one.append(change[i+1]-change[i])
'''
'''
arr = [1, 4]
for i in range(1, 55):
    arr.append(arr[-1] + (3*(2**i) - 2))
    d = arr[-1] - arr[-2]
    arr.append(2*(arr[-1]+d))
'''
arr = [1, 4, 8, 24, 34, 88, 110, 264, 310, 712, 806, 1800, 1990, 4360, 4742, 10248, 11014, 23560, 25094, 53256, 56326, 118792, 124934, 262152, 274438, 573448, 598022, 1245192, 1294342, 2686984, 2785286, 5767176, 5963782, 12320776, 12713990, 26214408, 27000838, 55574536, 57147398, 117440520, 120586246, 247463944, 253755398, 520093704, 532676614, 1090519048, 1115684870, 2281701384, 2332033030, 4764729352, 4865392646, 9932111880, 10133438470, 20669530120, 21072183302, 42949672968, 43754979334, 89120571400, 90731184134, 184683593736, 187904819206, 382252089352, 388694540294, 790273982472, 803158884358, 1632087572488, 1657857376262, 3367254360072, 3418793967622, 6940667150344, 7043746365446, 14293651161096, 14499809591302, 29411936043016, 29824252903430, 60473139527688, 61297773248518, 124244813938696, 125894081380358, 255086697644040, 258385232527366, 523367534821384, 529964604588038, 1073123348709384, 1086317488242694, 2199023255552008, 2225411534618630, 4503599627370504, 4556376185503750, 9218305487273992, 9323858603540486, 18858823439613960, 19069929672146950, 38562071809359880, 38984284274425862, 78812993478983688, 79657418409115654, 161003686678495240, 162692536538759174, 328762772798046216, 332140472518574086, 671036344478203912, 677791743919259654, 1369094286720630792]
def solve():
    N = int(input())
    for i in range(len(arr)-1):
        if arr[i] <= N < arr[i+1]:
            print('kidw0124' if i % 2 == 0 else 'eoaud0108')
            return
T = int(input())
for _ in range(T):
    solve()