11447. 최솟값의 인덱스

Jeuk Oh·2021년 8월 20일

코딩문제풀이

목록 보기

3/14

문제

설명

N개의 정수 F1,F2,...FN이 주어진다. $X_i$ 는 [0,Fi) 에 속한 실수를 모든 실수에 대해 동일한 확률로 하나 선택한 값이라고 하자. $argmin_{1≤i≤N}{X_i}$ 의 기댓값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.
두 번째 줄에는 N개의 정수 F1,F2,...FN (1 ≤ Fi ≤ 106)이 공백 하나로 구분되어 주어진다.

출력

각 테스트 케이스마다 $argmin_{1≤i≤N}{X_i}$ 의 기댓값을 출력한다. 정답과의 절대/상대 오차가 10^-8 이하이면 정답으로 인정된다.

예제

입력

출력

#1 2
#2 1.5
#3 2.5

아이디어

이게 뭔 문제여, 하고 시작한 문제. 어렵다!

문제 이해부터 하고 넘어가자면, 2번째 예제 [1,2,3]에서 $X_1$ 이 argmin이 되는 확률은

$\int_{0}^{1} \frac{dx(2-x)(3-x)}{1*2*3}$

으로 나타낼 수 있다. X1은 0~1 사이 값을 가지고, X2와 X3은 주어진 구간에서 X1보다 커야하기 때문이다.

이러한 방법으로 모든 확률을 구해서 E(i) = $\sum i*f(i)$ 를 하면 되는 문젠데..

그냥 수치적분으로 다 때려서 계산했더니 역시나 시간 초과! 뭔가 수학적인 테크닉이 더 필요해보인다.

구현

def integral(ex, function, i, dx=0.001):
    anw = 0
    for _ in range(0, int(ex * (1 / dx))):
        s, e = _ * dx + (1e-10), (_ + 1) * dx + (1e-10)
        anw += (function(i, s) + function(i, e)) * dx / 2

    return anw
    
def functionmaker(num_list):
    def main_function(x):
        anw = 1
        for i in num_list:
            anw *= (i - x) / i

        return anw
    def sub_function(i, x):
        anw = main_function(x)
        anw *= 1 / (i - x)

        return anw

    return sub_function
for tc in range(1, int(input()) + 1):
    int(input())
    num_list = list(map(int, input().split()))
    min_value = min(num_list)
    anw = 0
    function = functionmaker(num_list)

    for idx, value in enumerate(num_list):
        anw += (idx + 1) * integral(min_value, function, value)

    print("#{}".format(tc), "{:.8f}".format(anw))

sympy 마렵다..

구조를 생각해보니 N이 3개라면

X1에 대해서 $1*(F2-x)(F3-x)/(F1*F2*F3)$
X2에 대해서 $2*(F1-x)(F3-x)/(F1*F2*F3)$
X3에 대해서 $3*(F1-x)(F2-x)/(F1*F2*F3)$

을 다 적분하여 더한 값이 기대값이 되므로

처음부터

$(F1-x)(F2-x)(F3-x)/(F1*F2*F3)$

값을 구해놓고, i번째 연산에 따라서 Fi-x를 나눠주고 적분 시작..
아마 $(F1-x)(F2-x)(F3-x)/(F1*F2*F3)$ 이 값을 다른 x와 다른 i가 들어올때마다
새로 연산하는 부분에서 당연하게 시간초과가 난듯하다.

(x-Fi)꼴의 N개의 다항식이므로 어떻게 잘 전개를해서 수치적분을 안해도 될 것 같지만, 그것도 연산량이 많을 듯 하여 일단 패스

이미 구한 식을 저장하는 방법을 잘 쓰면 어떻게 잘 통과할 수 있을 듯 하다.

일단 예제는 잘 맞춰서 만족하고 마무리!

실행

입력

출력

#1 2.00000006
#2 1.50000017
#3 2.50000017

느낀 점

C++로 통과하신 분의 코드를 보니 주석이 없어 해석이 어렵지만 메모리제이션을 잘 활용한 수치적분을 쓰신 것 같았다.
코드의 편의를 위해서 그냥 반복계산을 때려넣게 했는데 아마 접근은 크게 틀린 것 같진 않고 어떻게 잘하면 될 것 같기도...

예를 들어,

dp[N][num_dx] 1000x (min_value//dx) 크기의 dp를 만든 뒤, 이 dp는 i번째 식의 dx구간에서 함수 값을 저장하게 한다.

x1에 대해서 $(F2-x)(F3-x)/(F1*F2*F3)$ 의 x=dx, 2dx값을 dp[0][0], dp[0][1] 저장하고... dp[0][num_dx]까지 다 한 뒤

(dp[0][0]/2 + sum(dp[0][1:num_dx-1]) + dp[0][-1]/2)*dx 를 하면 적분 값 하나 완성

다음으로 x2에 대한 $(F1-x)(F3-x)/(F1*F2*F3)$ 를 계산할 땐, dp[1][0]은 dp[0][0]에다가 (F1-dx)/(F2-dx) 만 곱하면 완성..

아마 근데 시간초과가 또 뜰 것 같은데.. 이거보단 당연히 빠를려나?

추가

앞서 생각한 방법으로 일단 13개의 테스트 케이스는 맞았다.

for tc in range(1, int(input()) + 1):
    N=int(input())
    num_list = list(map(int, input().split()))
    min_value = min(num_list)
    anw = 0
    num_dx = 1000
    dx = min_value/num_dx
    dp = [[0]*(num_dx) for _ in range(N)]
    for idx in range(num_dx):
        x = dx*idx+(1e-16)
        height = 1
        for j in range(1,N):
            height *= (num_list[j]-x)/num_list[j]
        dp[0][idx] = height/num_list[0]

    for i in range(1,N):
        for idx in range(num_dx):
            x = dx*idx+(1e-16)
            dp[i][idx] = dp[i-1][idx]*((num_list[i-1]-x)/(num_list[i]-x))

    for i in range(N):
        #anw += (i+1)*((dp[i][0]/2+sum(dp[i][1:-1])+dp[i][-1]/2))*dx
        anw += (i+1)*(dp[i][0]+dp[i][-1]+4*sum(dp[i][1:-1:2])+2*sum(dp[i][2:-2:2]))*dx/3


    print("#{}".format(tc), "{:.8f}".format(anw))