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_kb_k\)원을 배당금으로 지급하므로, 초기에 비해 \(s-a_kb_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_ib_i\)이다. 따라서 준혁이가 버는 돈의 기댓값은 다음과 같다.

\[E=\sum_{i=1}^n\frac{a_i}s(s-a_ib_i)=\sum_{i=1}^na_i-\frac1s \sum_{i=1}^na_i^2b_i=s-\frac1s\sum_{i=1}^n a_i^2b_i\]

\(s\)는 정해져 있으므로, \(E\)를 최소화하고 싶으면 \(\sum_1^na_i^2b_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_iy_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^2b_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^{\frac1m}\left(\sum_1^n a_i^{\frac{2m}{m-1}}\right)^{\frac{m-1}{m}}=X\]

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

 

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

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

\(\nabla f({\bf b})\)의 \(i\)번째 성분은 \(a_i^2\)이고, \(\nabla g({\bf b})\)의 \(i\)번째 성분은 \(mb_i^{m-1}\)이다. 따라서, 라그랑주 승수법에 의하여 모든 \(i\)에 대해서 \(a_i^2=\lambda mb_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^na_i^{\frac{2m}{m-1}}=\mu^{\frac{m}{m-1}}\sum_1^nb_i^m=t\mu^{\frac{m}{m-1}}\)이 된다. \(\mu\)를 구하기 위한 모든 값은 주어졌으므로 \(\mu\)를 계산할 수 있다.

게다가 \(\nabla f({\bf b})=\lambda \nabla g({\bf b})\)인 점에서는 \(a_i^2b_i=\mu b_i^m\)이므로, \(f({\bf b})=\sum_1^n a_i^2 b_i=\mu\sum_1^nb_i^m=t\mu\)이기까지 하다. 따라서 \(E\)의 최솟값은 \(s-\frac1s f({\bf b})=s-t\mu\)이 된다.

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

 

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