[Python] 32232번 엉엉이의 저주 탈출

 

 

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

---

 

24/09/13

 

 

맷코컵 검수 당시 검수했던 문제 중 하나이다. 문제 해석을 잘 한다면 막혔던 부분이 뚫리면서 쉽게 문제를 해결할 수 있을 것이다.

---

 

문제 접근 방식:

 

 

먼저 많은 관찰을 통해 다음과 같은 두 가지 사실을 발견해야 한다.(물론 오일러 지표를 통해 직접 유도하고 증명해도 충분하다.)

 

1. 엉엉이와 현철이가 지금까지 뽑은 서로 다른 점의 개수가 짝수 개라면 면이 홀수 개로 분할되고, 홀수 개라면 면이 짝수 개로 분할 된다.

 

2. 현철이는 자신이 이전에 뽑았던 점을 다시 뽑음으로써 홀짝성을 조정할 수 있다.

 

내가 이 문제에서 가장 어렵다고 느꼈던 점은 현철이와 엉엉이 모두 동일한 "확률"로 정수를 뽑는 상황, 즉, 게임에 랜덤이 개입되고, 서로가 서로를 보지 못하는 상황임에도 불구하고 현철이가 "최적의 전략"으로 게임을 한다는 것이었다.

 

이를 이해하기 위해 다음과 같은 예시를 들어보자.

주먹을 $1/3$확률로 내고 보를 $2/3$확률로 내는 상대방과 가위바위보를 하려고 한다. 상대방이 주먹을 내던 보를 내던 나는 볼 수 없는 상황이라고 하자. 내가 할 수 있는 최적의 전략은 무엇일까?  

 

이러한 상황에서 내가 할 수 있는 최적의 전략은 다음과 같다.

 

먼저, 상대방은 확정적으로 가위를 내지 않음을 나는 알고있다. 따라서 내가 주먹을 내는 행위는 지거나 비기는 결과만 가져다 주기 때문에, 주먹을 내서는 안된다.

 

따라서, 나는 보를 내거나 가위를 내야한다. 어떠한 비율로 내야할까를 생각해보자.

 

내가 보를 내는 확률을 $p$, 가위를 내는 확률을 $q$라고 하면, 다음과 같은 확률로 내가 이길 수 있다.

$$\frac{p}{3}+\frac{2q}{3}$$

 

근데 나는 $p + q = 1$임을 알고 있으므로, 식을 정리하면 다음과 같다.

$$\frac{p}{3}+\frac{2(1-p)}{3}=\frac{2-p}{3}$$

 

따라서 이를 최대화 하는 경우는 $p=0, q=1$일 때이다. 즉, 보를 이기는 가위만 내면 충분하다.

 

상대방은 높은 확률로 보를 내므로, 이에 맞춰서 나도 보를 이기는 가위만 내면 높은 확률로 이긴다는 뜻이다. 그리고 내가 이기는 확률은 상대방이 보를 내는 확률과 동일하다. (즉, 높은 확률을 따라간다.)

 

 

위와 비슷한 상황으로, 현철이와 엉엉이는 서로 게임을 하는데 서로의 결과를 모른다. 하지만 현철이는 최적의 플레이를 한다고 그랬다.

 

현철이가 알고 있는 정보는 현철이와 엉엉이가 모두 사용하는 게임 상수 $M$과 게임의 턴 수 $N$이므로, 이것에 의해 엉엉이가 지금까지 뽑은 점의 개수가 짝수 개인지 홀수 개인지에 관한 확률이 정해지고, 현철이는 그에 따라 행동한다고 추측할 수 있다.

 

위의 예시처럼 엉엉이가 지금까지 뽑은 점의 개수가 짝수 개일 확률 $p_1$와 홀수 개일 확률 $q_1$이 주어져있다고 하자.

 

현철이는 홀짝성을 조정할 수 있으므로, 현철이가 지금까지 뽑은 서로 다른 점의 개수가 짝수 개일 확률 $p_2$와 홀수 개일 확률 $q_2$를 조정할 수 있다는 뜻이다.

 

이는 위의 예시와 마찬가지로, $p_1$과 $q_1$중 높은 확률이 현철이가 게임에서 이길 확률과 동일한 확률이 될 것이다. 즉, 현철이가 게임에서 이길 확률은 엉엉이가 뽑은 점 개수의 홀짝성 확률 중 높은 확률과 동일한 확률이 된다.

 

 

먼저, $M$이 짝수인 경우를 보자.

 

$\{3, 4, \dots, M\}$중에서 홀수를 뽑을 확률은 $1/2$이고, 짝수를 뽑을 확률은 $1/2$이다.

 

즉, 한 턴에서 엉엉이가 홀수 개의 점을 추가할 확률은 $1/2$, 짝수 개의 점을 추가할 확률은 $1/2$이다.

 

홀수+홀수는 짝수, 짝수+짝수는 짝수이고 그 외의 경우는 홀수이므로, 매 턴을 거듭해도 점 개수의 총합의 홀짝성은 $1/2$로 동일하다.

 

따라서 $500 \ 000 \ 004$를 출력하면 충분하다.

 

$M$이 홀수인 경우를 보자.

 

$\{3, 4, \dots, M\}$중에서 홀수를 뽑을 확률은 $(M-1)/(2M-4)$이고, 짝수를 뽑을 확률은 $(M-3)/(2M-4)$이다.

 

즉, 한 턴에서 엉엉이가 홀수 개의 점을 추가할 확률은 $(M-1)/(2M-4)$, 짝수 개의 점을 추가할 확률은 $(M-3)/(2M-4)$이다.

 

 

만약 $N = 1$, 즉, 한 번만 턴을 진행한다면, 현철이는 자신이 이전에 뽑았던 점을 뽑음으로써 홀짝성을 조정할 수 없다.

 

이 경우, 그냥 처음에 엉엉이가 짝수 개의 점을 뽑고 현철이가 홀수 개의 점을 뽑는 경우던지, 아니면 엉엉이가 홀수 개의 점을 뽑고 현철이가 짝수 개의 점을 뽑는 경우만 현철이가 이긴다.

 

따라서 $\frac{(M-1)(M-3)}{(2M-4)(M-2)}$가 정답이 된다. (출력할 때 모듈로 역원을 통해 정수 값을 출력하자.)

 

 

홀수를 뽑을 확률을 편의 상 $p$라고 하면 짝수를 뽑을 확률은 $1-p$이다.

 

총 합이 짝수일 확률은 홀수를 짝수번 뽑으면 총 합이 짝수가 되므로, 다음과 같이 정리할 수 있다.

$$\sum_{k = \text{even}} {N \choose k}p^{k}(1-p)^{N-k}$$

 

마찬가지로, 총 합이 홀수일 확률은 홀수를 홀수번 뽑으면 되므로, 다음과 같이 정리할 수 있다.

$$\sum_{k = \text{odd}} {N \choose k}p^{k}(1-p)^{N-k}$$

 

잘 관찰하면 이것이 이항분포라는 사실을 확인할 수 있다. 따라서 이항분포를 빠르게 계산하는 다양한 방법을 통해 구현하면 된다.

 

나의 경우 식정리를 통해 다음과 같이 간단하게 만들었다.

 

만약 $N$이 짝수라면, 둘 중에 더 큰 확률은 총 합이 짝수일 확률이다.

 

따라서 이를 다음과 같이 정리할 수 있다.

$$\begin{align}& \sum_{k = \text{even}} {N \choose k}p^{k}(1-p)^{N-k}\\ =& \sum_{k=0}^{N} {N \choose k}p^{k}(1-p)^{N-k} \frac{1+(-1)^{k}}{2} \\ =& \frac{1}{2} \left( \sum_{k=0}^{N} {N \choose k} p^{k} (1-p)^{N-k} + \sum_{k=0}^{N} {N \choose k} (-p)^{k} (1-p)^{N-k} \right) \\ =& \frac{1}{2} \left( 1 + (1-2p)^{N} \right) \end{align}$$

 

이 식을 모듈로 역원을 사용하여 정수로 출력하면 된다.

 

만약 $N$이 홀수라면, 둘 중에 더 큰 확률은 총 합이 홀수일 확률이다.

 

따라서, 비슷하게 다음과 같이 정리할 수 있다.

$$\begin{align}& \sum_{k = \text{odd}} {N \choose k}p^{k}(1-p)^{N-k}\\ =& \sum_{k=0}^{N} {N \choose k}p^{k}(1-p)^{N-k} \frac{1-(-1)^{k}}{2} \\ =& \frac{1}{2} \left( \sum_{k=0}^{N} {N \choose k} p^{k} (1-p)^{N-k} - \sum_{k=0}^{N} {N \choose k} (-p)^{k} (1-p)^{N-k} \right) \\ =& \frac{1}{2} \left( 1 - (1-2p)^{N} \right) \end{align}$$

 

이를 출력하면 답이 된다.

---

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

import sys
input = sys.stdin.readline
MOD = 1_000_000_000 + 7

T = int(input())
def solve(N, M):
    if M % 2 == 0: # M이 짝수인 경우
        return 500_000_004
    if N == 1: # N이 1인 경우
        numer = (M-1)*(M-3)%MOD
        denom = (2*M-4)*(M-2)%MOD
        return numer*pow(denom, -1, MOD)%MOD
    # M은 이미 홀수이다.(즉, 홀수를 뽑을 확률이 더 크다.)
    p = (M-1)*pow(2*M-4, -1, MOD)%MOD
    if N % 2 == 0:
        ans = (1 + pow((1-2*p)%MOD, N, MOD))*500_000_004%MOD
    else:
        ans = (1 - pow((1-2*p)%MOD, N, MOD))*500_000_004%MOD
    return ans

for _ in range(T):
    print(solve(*map(int, input().split())))