BOJ 31540 - 도박 문제 전문 상담은 국번없이 1336 (Python3)

1을 타패하고 33을 또이쯔로 쓰겠다.

며칠 전 대회인 제4회 MatKor의 H번 문제이다. 총 16문제짜리 셋이었으니, 이 뒤로 이것보다 어려운 문제가 8개나 있다는 뜻이다. 이 문제 난이도도 절대 만만하지 않다! 본대회에서 식 정리하는 데만 20분을 넘게 썼다.

내 영역이라서 그나마 빠르게 풀기는 했는데, 그 빠르게 푼다는 게 40분 조금 넘게 걸렸던 문제다. 쏟은 시간 보고 제법 만만치 않으리라고 생각했는데 설마 Platinum I이었을 줄은...

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

2024년 3월 9일 제4회 MatKor Cup이 개최된다. 이번 MatKor Cup에는 총 $n$명이 참가했고, 각 참가자는 $1$번부터 $n$번까지의 번호가 붙어있다.

이번 대회 운영진인 준혁이는 어떤 참가자가 우승할 지에 대해 자신을 제외한 운영진끼리 베팅을 하도록 했다. 베팅 결과 ‘$i$번 참가자가 우승한다’에 $a_i$원의 금액이 걸렸고, 총 $s=a_1+a_2+\cdots +a_n\ne 0$원의 금액이 걸렸다. 실제로 $i$번째 사람이 우승할 확률은 베팅 금액에 비례하는 $\frac{a_i}{s}$이다. 우승자는 반드시 한 명이다.

도박을 싫어해 베팅에 참여하지 않은 종우는 자신이 공평하게 배당을 나눌 수 있다고 말했다. 그 결과, 종우가 배당을 정하기로 했다.

$i$번 참가자의 배당이 $b_i$라고 할 때, 배당 상수 $m$과 $t$에 대해 배당의 총합이 $t=b_1^m+b_2^m+\cdots +b_n^m$가 되도록 $b_i$들을 정하고자 한다. 이때 두 배당 상수는 양의 정수이고, 각 참가자의 배당은 음이 아닌 실수이다.

만약 $k$번 참가자가 우승한다면, 준혁이는 $k$번 참가자에 베팅한 사람들이 건 돈의 $b_k$배를 각각 배당금으로 지급한다. 즉, $k$번 참가자가 우승할 경우 받은 $s$원에서 $a_k{b}_k$원을 배당금으로 지급하므로, 초기에 비해 $s-a_k{b}_k$원을 벌게 된다. 만약 이 값이 음수라면, 그 절댓값만큼의 돈을 잃게 된다.

종우는 준혁이가 도박 운영을 통해 돈을 버는 것을 못마땅하게 생각해 준혁이가 최대한 돈을 벌지 못하게 하고 싶다. 참가자별로 걸린 금액과 배당 상수가 주어질 때 종우를 도와 준혁이가 버는 금액의 기댓값이 최소가 되도록 배당을 조정해 보자.

 

입력

첫 번째 줄에 대회 참가자의 수 $n$, 배당의 총합을 결정할 상수 $m,t$가 공백으로 구분되어 주어진다. $(1\le n,m,t\le {10}^6)$

두 번째 줄에 베팅 결과 각 참가자에게 걸린 금액을 나타내는 $n$개의 정수 $a_i$가 공백으로 구분되어 주어진다. $(0\le a_i\le 1000)$

주어지는 입력은 $s>0$을 만족한다.

 

예제 입력)

# 예제 입력 1
1 1 1
10

# 예제 입력 2
2 2 2
1 1

# 예제 입력 3
2 2 2
0 10

# 예제 입력 4
2 1 3
4 5

# 예제 입력 5
2 2 6
1 1

# 예제 입력 6
4 3 123456
999 987 975 951

 

출력

준혁이가 버는 금액의 기댓값의 최솟값을 출력한다. 이 값이 음수일 수 있음에 유의하자.

정답과의 절대오차 또는 상대오차가 ${10}^{-6}$ 이하이면 정답으로 인정된다.

 

예제 출력)

# 예제 출력 1
0

# 예제 출력 2
1

# 예제 출력 3
-4.1421356237

# 예제 출력 4
0.6666666667

# 예제 출력 5
0.2679491924

# 예제 출력 6
-26785.85891

 

---

내 코드

n,m,t = map(int,input().split())
a = list(map(int,input().split())); s = sum(a)
if n == 1:
    print(a[0]-a[0]*pow(t,1/m))
    exit(0)
if m == 1:
    print(s-t*max(a)**2/s); exit(0)
p = [i/s for i in a]
u,v = 2*m/(m-1),(m-1)/m
alpha = sum(pow(i,u) for i in p)/t
alpha = pow(alpha,v)
print(s*(1-t*alpha))

 

$n=1$인 케이스는 $b_n$이 이미 결정된 것이나 다름없다. 계산만 해 주고 끝내면 된다. $m=1$일 때는 가장 고액이 걸린 사람에게 몰빵해주는 것이 제일 이득이다. 자명한 케이스들은 쉽게 계산할 수 있으니, 자명하지 않은 케이스인 $n,m>1$에 대해서 풀어 보자. 두 가지의 풀이가 있다. 사전지식을 많이 요구하고 계산이 많은 풀이 하나, 사전지식을 엄청나게 많이 요구하지만 계산은 적은 풀이 하나.

일단 풀이과정에 들어가기 전에 식을 어떻게 변형시켜야 할지 알아보자. $i$번 참가자가 우승할 확률은 $\frac{a_i}{s}$이고, 그 때 준혁이가 버는 돈은 $s-a_i{b}_i$이다. 따라서 준혁이가 버는 돈의 기댓값은 다음과 같다.

$$E=\sum _{i=1}^n\frac{a_i}{s}(s-a_i{b}_i)=\sum _{i=1}^n{a}_i-\frac{1}{s}\sum _{i=1}^n{a}_i^2{b}_i=s-\frac{1}{s}\sum _{i=1}^n{a}_i^2{b}_i$$

$s$는 정해져 있으므로, $E$를 최소화하고 싶으면 $\sum _1^n{a}_i^2{b}_i$를 최대화하면 된다. 간단해 보이는 optimization problem으로 문제가 바뀐다. Constraint는 $t=\sum _1^n{b}_i^m$이다.

 

후자는 횔더 부등식(Hölder Inequality)를 쓴다. 수학 전공자라도 저학년이면 볼 일이 없을 것이고, 전공자가 아니라면 더더욱 볼 일이 없는 완전한 사전지식의 영역이다. 본래는 가측함수의 적분값에서 쓰이는데, 수열에서도 사용 가능하다. 두 양수 $p,q$가 $p^{-1}+q^{-1}=1$일 때 양수로만 이루어진 $n$-tuple $(x_1,\cdots ,x_n),(y_1,\cdots ,y_n)$에 대하여 다음 식이 성립한다는 것이 바로 횔더 부등식이다.

$$\sum _1^n{x}_i{y}_1\le {\left(\sum _1^n{x}_i^p\right)}^{p^{-1}}{\left(\sum _1^n{y}_i^q\right)}^{q^{-1}}$$

$q=m$으로, $x_i=a_i^2,y_i=b_i$로 두면 $p=(1-q^{-1}{)}^{-1}=\frac{m}{m-1}$이 되며, 횔더 부등식은 다음과 같이 바뀐다.

$$\sum _1^n{a}_i^2{b}_1\le {\left(\sum _1^n{a}_i^{\frac{2m}{m-1}}\right)}^{\frac{m-1}{m}}{\left(\sum _1^n{b}_i^m\right)}^{m^{-1}}=t^{\frac{1}{m}}{\left(\sum _1^n{a}_i^{\frac{2m}{m-1}}\right)}^{\frac{m-1}{m}}=X$$

계산하는 데 필요한 모든 값이 주어져 있으므로 $X$는 금방 계산할 수 있다. $E$의 최솟값은 $s-\frac{X}{s}$이다.

 

그런데 횔더 부등식을 외우고 있는 사람은 많지 않을 뿐더러 저 상황에서 횔더 부등식이 생각나서 그대로 풀 수 있는 사람이 몇 명이나 될까. 난 없으리라 본다. 대신 이공계 대학생에게 조금이나마 더 익숙할 기법을 사용할 것이다. 라그랑주 승수법이다.

함수 $f(\mathbf{b})=\sum _1^n{a}_i^2{b}_i$와 constraint $g(\mathbf{b})=-t+\sum _1^n{b}_i^m$에서, $g(\mathbf{b})=0$을 만족할 때의 $f(\mathbf{b})$의 극값은 $\mathrm{\nabla }f(\mathbf{b})=\lambda \mathrm{\nabla }g(\mathbf{b})$인 점에서 발생한다는 것이 라그랑주 승수법이다. 일단 횔더 부등식보다는 잘 알려져 있으며, 대부분의 대학에서 공통으로 배우는 미적분학에서 위와 같이 constaint가 하나인 꼴의 라그랑주 승수법은 가르치는 것으로 안다.

$\mathrm{\nabla }f(\mathbf{b})$의 $i$번째 성분은 $a_i^2$이고, $\mathrm{\nabla }g(\mathbf{b})$의 $i$번째 성분은 $m{b}_i^{m-1}$이다. 따라서, 라그랑주 승수법에 의하여 모든 $i$에 대해서 $a_i^2=\lambda m{b}_i^{m-1}$이어야 한다.

따라서 $\lambda m=\mu$로 두면, $a_i^{\frac{2m}{m-1}}={\left(\mu b_i^{m-1}\right)}^{\frac{m}{m-1}}={\mu }^{\frac{m}{m-1}}{b}_i^m$이다. 양 변을 $i=1$부터 $i=n$까지 더해 주면, $\sum _1^n{a}_i^{\frac{2m}{m-1}}={\mu }^{\frac{m}{m-1}}\sum _1^n{b}_i^m=t{\mu }^{\frac{m}{m-1}}$이 된다. $\mu$를 구하기 위한 모든 값은 주어졌으므로 $\mu$를 계산할 수 있다.

게다가 $\mathrm{\nabla }f(\mathbf{b})=\lambda \mathrm{\nabla }g(\mathbf{b})$인 점에서는 $a_i^2{b}_i=\mu b_i^m$이므로, $f(\mathbf{b})=\sum _1^n{a}_i^2{b}_i=\mu \sum _1^n{b}_i^m=t\mu$이기까지 하다. 따라서 $E$의 최솟값은 $s-\frac{1}{s}f(\mathbf{b})=s-t\mu$이 된다.

실수 오차는 생각보다 관대한 편이고, 파이썬으로 푼다면 실수 오차에 당하지 않기 위해 decimal을 꺼내는 순간 시간초과에 막히게 된다. 그냥 정직하게 풀어도 통과한다. 내가 그랬다.

 

이로서 31540번의 풀이를 마친다.