TCO20 Round 1A Hard-BlindBoxSets

問題のリンク

問題概要

N個の景品から成るコンプガチャがあり当選確率はいずれも同様に確からしい。全ての景品をM個以上手に入れるまでの操作回数の期待値を求めよ。

制約

• 
• 

解法

が小さいのでのDPが間に合う。

を1個揃ってるのが 種類、2個揃ってるのが 種類、3個揃ってるのが 種類、4個以上揃ってるのが 種類の時の操作回数の期待値と定義する。

遷移は次の通りである。

\begin{eqnarray*} \small dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack \lbrack l \rbrack &=& \small \frac{i}{N}\left(dp\lbrack i-1 \rbrack \lbrack j \rbrack \lbrack k \rbrack \lbrack l \rbrack + 1\right) + \frac{j}{N}\left(dp\lbrack i+1 \rbrack \lbrack j-1 \rbrack \lbrack k \rbrack \lbrack l \rbrack + 1\right) + \frac{k}{N}\left(dp\lbrack i \rbrack \lbrack j+1 \rbrack \lbrack k - 1 \rbrack \lbrack l \rbrack + 1\right) + \frac{l}{N}\left(dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k+1 \rbrack \lbrack l - 1 \rbrack + 1\right) + \frac{N-i-j-k-l}{N}\left(dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack \lbrack l \rbrack + 1\right) \\ &=& \small \frac{N}{i+j+k+l} \left( 1 + \frac{i}{N} \cdot dp\lbrack i-1 \rbrack \lbrack j \rbrack \lbrack k \rbrack \lbrack l \rbrack + \frac{j}{N} \cdot dp\lbrack i+1 \rbrack \lbrack j-1 \rbrack \lbrack k \rbrack \lbrack l \rbrack + \frac{k}{N} \cdot dp\lbrack i \rbrack \lbrack j+1 \rbrack \lbrack k - 1 \rbrack \lbrack l \rbrack + \frac{l}{N} \cdot dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k+1 \rbrack \lbrack l - 1 \rbrack \right) \end{eqnarray*}

実装

double dp[55][55][55][55];

class BlindBoxSets {
  public:
  double expectedPurchases(int numSets, int numItems) {
    int n=numItems,m=numSets;
    for(int l=0;l<=n;l++){
      for(int k=0;k+l<=n;k++){
        for(int j=0;j+k+l<=n;j++){
          for(int i=0;i+j+k+l<=n;i++){
            if(i+j+k+l==0)continue;
            double d=1.0;
            if(i)d+=(i/(double)n)*dp[i-1][j][k][l];
            if(j)d+=(j/(double)n)*dp[i+1][j-1][k][l];
            if(k)d+=(k/(double)n)*dp[i][j+1][k-1][l];
            if(l)d+=(l/(double)n)*dp[i][j][k+1][l-1];
            d/=(i+j+k+l)/(double)n;
            dp[i][j][k][l]=d;
          }
        }
      }
    }
    if(m==1) return dp[n][0][0][0];
    else if(m==2) return dp[0][n][0][0];
    else if(m==3) return dp[0][0][n][0];
    else return dp[0][0][0][n];
  }
};