[Python] 31540번 도박 문제 전문 상담은 국번없이 1336

 

 

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

31540번: 도박 문제 전문 상담은 국번없이 1336

---

 

24/03/10

 

 

내가 검수했던 MatKor컵의 한 문제로, 전형적인 수학 문제이다.

 

두 가지 방법으로 풀 수 있는 좋은 문제이다. 여기서는 의도했던 정해를 중점으로 서브태스크 순으로 따라가며 설명해보고자 한다.

---

 

문제 접근 방식:

 

 

문제를 요약하면, 준혁이는 도박을 운영하는 도박 운영자고, 사람들에게 받은 돈이 총 $S$원이다.

 

참가자들 중에서 $i$번째 참가자가 우승한다면, 준혁이는 우승한 참가자를 맞춘 사람에게 그 사람이 건 돈의 $b_i$배를 돌려주어야 한다.

 

$i$번째 참가자에게 걸린 돈의 총 합은 $a_i$이다. 즉, 준혁이는 $i$번째 참가자가 우승한다면 $a_ib_i$원을 잃는다.

 

따라서, 준혁이는 $S$원을 받고 $a_ib_i$원을 돌려줘야 하므로 $S - a_ib_i$원을 얻는다.

 

만약 저 값이 음수면 $|s - a_ib_i|$원을 잃는다고 볼 수 있다.

 

$i$번째 참가자가 우승할 확률은 $a_i / S$이다. 또한, 문제에서 주어진 제약 조건은 $\sum_{i=1}^n {b_i}^m = t$이다. 이때, $m$과 $t$는 정해진 상수이다.

 

우리의 목적은 준혁이가 얻을 수 있는 금액의 기댓값이 최소화가 되도록 만드는 것이다. 즉, 수식으로 표현하면, $\sum_{i = 1}^{n}\frac{a_i}{S}\cdot (S - a_ib_i)$ $=$ $\sum_{i = 1}^{n} a_i - \frac{(a_i)^2b_i}{S}$ $=$ $S - \frac{1}{S} \sum_{i=1}^{n} {a_i}^2 b_i$가 최소화되도록 만들어야 한다.

 

 

• 첫 번째 서브태스크 ($n = 1$)

$n = 1$인 경우, $S = a_0$이고, ${b_0}^m = t \rightarrow b_0 = \sqrt[m] {t}$이다.

 

따라서, 준혁이가 얻을 수 있는 금액의 기댓값은 $S - \frac{1}{S} \sum_{i=1}^{n} {a_i}^2 b_i$ $=$ $a_0 - a_0\sqrt[m]{t}$가 된다.

 

이 값을 그대로 출력해주면 $8$점을 얻을 수 있다.

 

 

• 두 번째 서브태스크 ($n = 2$)

$n = 2$인 경우이다. 이때는 $t = {b_0}^m + {b_1}^m$이고, $b_0$가 정해지면 $b_1$도 정해짐을 확인할 수 있다.

 

따라서, ${b_1}^m = t - {b_0}^m \Rightarrow b_1 = \sqrt[m] {t - {b_0}^m}$임을 알 수 있다.

 

이를 이용해 준혁이가 얻을 수 있는 금액의 기댓값을 다음과 같이 정리할 수 있다.

 

$$S - \frac{1}{S} \sum_{i=1}^{n} {a_i}^2 b_i$$

$$= S - \frac{{a_0}^2b_0}{S} - \frac{{a_1}^2b_1}{S}$$

$$= S - \frac{{a_0}^2b_0}{S} - \frac{{a_1}^2b_1}{S}$$

$$= S - \frac{{a_0}^2b_0}{S} - \frac{{a_1}^2 \sqrt[m] {t-{b_0}^m} }{S}$$

 

이 함수는 가능한 $b_0$의 범위, 즉, $0 \leq b_0 \leq \sqrt[m]{t}$범위 안에서는 볼록 함수임을 확인할 수 있다.

 

이에 대한 증명은 아래에 쓰여있다.

식의 형태를 변형하여, ${b_0}^m = x$라고 하자.
주어진 식은 $S - \frac{{a_0}^2 \sqrt[m]{x}}{S} - \frac{{a_1}^2 \sqrt[m] {t-x} } {S}$이고, 가능한 $x$의 범위는 $0 \leq x \leq t$이다.

$y = S$, $y = - \frac{{a_0}^2 \sqrt[m]{x}}{S}$, $y = - \frac{{a_1}^2 \sqrt[m] {t-x} } {S}$는 모두 $0 \leq x \leq t$범위에서 볼록 함수이고, 볼록 함수의 합은 볼록 함수이므로, 이 함수는 볼록하다.

Lemma) 볼록 함수의 합은 볼록하다.
볼록 함수의 정의를 생각하자.
$f$가 $I$에서 볼록하다는 뜻은, 모든 $x, y \in I$와 $\alpha + \beta = 1, \alpha \geq 0, \beta \geq 0$을 만족하는 모든 $\alpha , \beta$에 대해서 $f(\alpha x + \beta y) \leq \alpha f(x) + \beta f(y)$를 만족함을 의미한다.
함수 $f$와 함수 $g$가 $I$에서 볼록하다고 하자.
$(f + g)(\alpha x + \beta y)$ $=$ $f(\alpha x + \beta y) + g(\alpha x + \beta y)$ $\leq$ $\alpha f(x) + \beta f(y) + \alpha g(x) + \beta g(y)$ $=$ $ \alpha (f+g)(x) + \beta (f+g)(y)$.
따라서, 볼록 함수의 합은 볼록하다.

 

볼록 함수에서 최솟값을 구하고자 할 때에는 삼분 탐색을 활용할 수 있다.

 

이 알고리즘을 통해 최솟값을 구할 수 있으며, 이를 통해 서브태스크 2를 해결할 수 있다.

 

 

• 세 번째 서브태스크 ($m = 1$)

$S - \frac{1}{S} \sum_{i=1}^{n} {a_i}^2 b_i$를 최소화시키는 것이 목적이므로, 결국 $\sum_{i=1}^{n} {a_i}^2 b_i$를 최대화시키면 충분하다.

 

$m = 1$이므로, $\sum_{i=1}^{n} b_i = t$이다.

 

위의 식을 최대화시키기 위해서는 ${a_i}^2$의 값이 가장 큰 인덱스 $i$에 대해서 $b_i = t$로 설정하고, 나머지 인덱스에 대해서는 $b_i$의 값을 $0$으로 설정해 주면 된다.

 

그 이유는 다음과 같다.

 

${a_i}^2$의 값이 가장 큰 인덱스를 $k$라고 하자.
어떤 양수 $p$에 대해서, $b_k = t - p$라고 해보자. 그러면 $b_k$를 제외한 $b_i$들의 합은 $p$가 된다.
${a_k}^2 t$와 ${a_k}^2 \cdot (t-p) + \sum_{i=0; i\neq k}^n {a_i}^2 b_i$을 생각해보자.
전자의 식은 ${a_i}^2$의 값이 가장 큰 인덱스 $k$에 대해서 $b_k = t$로 설정한 경우의 식이고, 후자는 그렇지 않은 경우의 식이다.
후자의 식을 전개하면 ${a_k}^2 t - {a_k}^2 \sum_{i=0; i\neq k}^n b_i + \sum_{i=0; i\neq k}^n {a_i}^2 b_i$이고, ${a_k}^2 \sum_{i=0; i\neq k}^n b_i > \sum_{i=0; i\neq k}^n {a_i}^2 b_i$이므로, 후자의 식이 전자의 식보다 항상 작음을 알 수 있다.

 

이에 따라, $\mathrm{max}(a) = M$이라고 두면, 위의 식은 $S - \frac{M^2 t}{S}$가 됨을 확인할 수 있다.

 

 

• 네 번째 서브태스크 ($m = 2$)

세 번째 서브태스크와 목적 자체는 동일하다. 결국 $\sum_{i=1}^{n} {a_i}^2 b_i$를 최대화시키면 된다.

 

또한, $m=2$이므로, $\sum_{i=1}^{n} {b_i}^2 = t$를 만족한다.

 

편의 상 ${a_i}^2 = c_i$라고 하자.

 

$\sum_{i=1}^{n} c_i b_i$를 최대화하고 싶고, $\sum_{i=1}^{n} {b_i}^2 = t$로 정해져 있으므로, 우리는 코시-슈바르츠 부등식을 생각해 볼 수 있다.

 

코시-슈바르츠 부등식은 다음과 같은 부등식이다.

 

$$\left( \sum_{i=1}^{n} c_i b_i \right) ^{2} \leq \left( \sum_{i=1}^{n} {c_i}^2 \right) \left( \sum_{i=1}^{n} {b_i}^2 \right)$$

 

즉, 좌변의 값을 최대화하고 싶다면 우변을 구하기만 하면 충분하다.

 

우리는 ${c_i}^2 = {a_i}^4$의 값들을 모두 구해서 더할 수 있고, ${b_i}^2$의 값들을 모두 더한 것이 $t$임을 알고 있으므로, 이를 통해 구할 수 있다.

 

$\sum_{i = 1}^{n} {a_i}^4 = K$라고 하자.

 

그렇다면, 구하고자 하는 값은 $S - \frac{\sqrt{Kt}}{S}$가 됨을 알 수 있다.

 

 

• 다섯 번째 서브태스크 (정해)

마지막 서브태스크는 코시-슈바르츠 부등식의 확장 버전인 횔더 부등식(Hölder Inequality)을 활용하여 풀거나, 라그랑주 승수법을 이용하여 해결할 수 있다.

 

결국 $\sum_{i=1}^{n} {a_i}^2 b_i$를 최대화시키는 것이 우리의 목적이고, $\sum_{i=1}^{n} {b_i}^m = t$라는 제약조건이 걸려있다.

 

횔더 부등식은 다음과 같은 부등식을 말한다.

 

$$\left( \sum_{i=1}^{n} a_i b_i \right) \leq \left( \sum_{i=1}^{n} {a_i}^p \right)^{1/p} \left( \sum_{i=1}^{n} {b_i}^q \right)^{1/q} ; 1/p + 1/q = 1, \forall a_i, b_i > 0$$

 

먼저 $m = 1$인 경우는 세 번째 서브태스크에서 처리했던 것과 같이 따로 처리해 준다.

 

$m \neq 1$인 경우를 살펴보자.

 

우리의 목적은 $\sum_{i=1}^{n} {a_i}^2 b_i$를 최댓값을 구하는 것이다.

 

이 최댓값은 횔더 부등식에 의하면, $\left( \sum_{i=1}^{n} ({a_i}^{2})^{p} \right)^{1/p} \left( \sum_{i=1}^{n} {b_i}^m \right)^{1/m}$이다.

 

이때, $1/p + 1/m = 1$이므로, $1/p = (m-1)/m$이고, $p = m/(m-1)$이다.

 

따라서, ${a_i}^{2m/(m-1)}$의 값들을 모두 더한 합을 $K$라고 한다면, 이 최댓값을 $K^{(m-1)/m}t^{1/m}$으로 나타낼 수 있다.

 

따라서 우리가 구하고자 하는 최솟값은 $S - \frac{K^{(m-1)/m}t^{1/m}}{S}$이 된다.

 

---

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

# 도박 문제 전문 상담은 국번없이 1336
import sys
input = sys.stdin.readline

n, m, t = map(int, input().rstrip().split())
a = list(map(int, input().rstrip().split()))
# subtask-1 (n=1)
# print(a[0] - a[0]*(t**(1/m)))
# Maybe_ac (feat. holder)
if m == 1:
    S = sum(a)
    K = max(a)
    ans = S - t*K*K/S
    print(ans)
else:
    S = sum(a)
    s = 2*m/(m-1)
    K = 0
    for i in range(n):
        K += (a[i]**s)
    K **= ((m-1)/m)
    ans = S - K*(t**(1/m))/S
    print(ans)