BOJ 12516 - 챔피언소트 (Large)

BOJ 12516 - 챔피언소트 (Large)

이 문제는 정답이 너무 쉽지만 증명이 까다롭다.

$E(X)=p_0E(0)+p_1E(1)+ \cdots +p_{X-1}E(X-1)+P_XE(X)+1$ 처럼 기댓값 식을 만들어주고

직접 정리하여 교란순열을 이용해 $p_i$ 값을 계산하고 DP를 $O(n^2)$으로 돌리면 $E(X)$에 대한 규칙을 찾을 수 있다.

특별한 경우로 $E(1)=1$ 이라고 두자.

// 제 자리가 아닌것이 i개가 있을 때 모두 제자리를 찾아가기위한 기댓값
double dp[1001], fac[1001], bino[1001][1001], perm[1001];
void pre_calc() {
   fac[0] = 1;
   for (int i = 1; i <= 1000; i++) fac[i] = fac[i - 1] * i;
   for (int i = 0; i <= 1000; i++)
      for (int j = 0; j <= i; j++)
         bino[i][j] = !i || !j ? 1 : bino[i - 1][j] + bino[i - 1][j - 1];
   perm[1] = 0;
   perm[2] = 1;
   for (int i = 3; i <= 1000; i++) perm[i] = (i - 1) * (perm[i - 2] + perm[i - 1]);
   dp[1] = 1;
   dp[2] = 2.0;
   // dp[i] = 1 + dp[0] * p[0] + dp[1] * p[1] + ... + dp[i] * p[i]
   // dp[i] = (1 + dp[0] * p[0] + dp[1] * p[1] + ... + dp[i-1] * p[i-1]) / (1 - p[i])
   for (int i = 3; i <= 1000; i++) {
      double all_case = fac[i];
      double sum = 1;
      double psum = 0;
      for (int j = 0; j <= i - 1; j++) {
         int correct = i - j;
         int not_correct = i - correct;
         double tmp = bino[i][correct] * perm[not_correct];
         double p = tmp / all_case;
         psum += p;
         sum += dp[j] * p;
      }
      dp[i] = sum / psum;
      for (int l = 1; l < i; l++) {
         int r = i - l;
         mina(dp[i], dp[l] + dp[r]);
      }
   }
}