[BOJ 13255] 동전 뒤집기

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

13255번: 동전 뒤집기

Tag : dp, combinatorics

 

문제요약

N개의 동전 중 \(A_i\)개를 랜덤으로 골라 뒤집는 작업을 N번 반복한다. 

이 때 앞면이 위인 동전 개수의 기댓값을 구하라.

 

풀이

확률 dp다. 주의할 점이 있다면 경우의 수를 dp의 정의로 잡고 쭉 구해놓고 답을 출력할 때만 표본을 나누면 

오버플로우때문에 문제가 된다. (long double에도 안들어간다) 이걸로 30분정도를 맞왜틀했다...

 

\(dp_{i, j} = \) i번째 뒤집기 이후 i개의 동전이 앞면을 향할 확률

이미 앞면을 향하는 동전이 k개이고 만들고 싶은 개수가 j라고 하자.

이 때 두가지 경우를 생각할 수 있다.

 

i) k < j

n - k개가 뒷면을 향하는 상태이니 일단 이 중 j - k개를 뒤집어 j개가 앞면을 향하게 만든다.

그 후 \(A_i\)개의 기회 중 남은 개수가 짝수라면 남은 것 중 앞면, 뒷면을 반반씩 뒤집어서 이를 상쇄할 수 있다.

그래서 이 경우의 수는 \( \binom{ n - k }{ (A_i + (j - k))/2 } * \binom{ k }{ (A_i - (j - k))/2 } \)가 된다.

 

ii) j \(\leq \) k

k개 중 k - j개를 뒷면으로 되돌려놔야한다. 

그러고 남은 것이 짝수일 때 앞면, 뒷면 중 반반씩을 골라 뒤집는다.

이 경우의 수는 \( \binom{ k }{ (A_i + (k - j))/2 } * \binom{ n - k }{(A_i - (k - j))/2} \)이다. 

 

이제 열심히 구현하면 된다.

시간복잡도는 \(O(KN^2)\)이다.

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

using ld = long double;

ld t[1010][1010];

void init() {
    for(int i=0; i<=1000; i++) {
        t[i][0] = 1;
        for(int j=1; j<=i; j++) {
            t[i][j] = t[i - 1][j] + t[i - 1][j - 1];
        }
    }
}

int n, day;
ll A[55];
ld dp[55][1010]; // dp[day][i]

ld ncr(int N, int R) {
    if(N < 0 or R < 0) return 0;
    if(N < R) return 0;
    return t[N][R];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    init();
    cin >> n >> day;
    for(int i=1; i<=day; i++) cin >> A[i];
    dp[0][n] = 1;
    for(int i=1; i<=day; i++) {
        for(int j=0; j<=n; j++) {
            for(int k=0; k<j; k++) {
                if((A[i] + (j - k)) % 2) continue;
                if(j - k > A[i]) continue;
                ld t = dp[i - 1][k] * ncr(n - k, (A[i] + (j - k)) / 2) * ncr(k, (A[i] - (j - k)) / 2);
                t /= ncr(n, A[i]);
                dp[i][j] += t;
            }
            for(int k=j; k<=n; k++) {
                if((A[i] + (k - j)) % 2) continue;
                if(k - j > A[i]) continue;
                ld t = dp[i - 1][k] * ncr(k, (A[i] + (k - j)) / 2) * ncr(n - k, (A[i] - (k - j)) / 2);
                t /= ncr(n, A[i]);
                dp[i][j] += t;
            }
        }
    }
    ld ans = 0;
    for(int i=0; i<=n; i++) ans += i * dp[day][i];
    cout << fixed << setprecision(20) << ans << endl;
}