保存されている過去のバージョンの一覧

2014年12月24日00時14分25秒

yukicoder No.108 - トリプルカードコンプ

Source

ニコニコミュニティ
問題文

問題概要

$N$ 種類のカードが有り，カード $k$ を現在 $A_k$ 枚持っている．
$1$ 枚カードを買うと，どれかの種類のカードが $1$ 枚当確率で手に入る．
全てのカードを $3$ 枚以上揃えるために必要なカードを買う枚数の期待値を求める問題．

解法

状態を（現在 $0$ 枚のカードの種類数，現在 $1$ 枚のカードの種類数，現在 $2$ 枚のカードの種類数）を状態にして，残り買うカードの枚数の期待値を計算するDPをすれば良い．
状態遷移は自己ループを含むが，既に $3$ 枚集まっているカードが $k$ 個の時，それ以外（引くと状態が変わる）のカードを引く確率は $(N-k)/N$ で，そのようなカードを引くまでに買うカードの枚数の期待値は $N/(N-k)$ であることを利用すれば簡単に解消できる．
時間計算量，領域計算量ともに $O(N^3)$．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}

int N, A[100];
double dp[120][120][120];

double solve(int a, int b, int c){
  int i, j, k, d = N - a - b - c;
  double res = 0, nx;

  if(dp[a][b][c] >= -0.5) return dp[a][b][c];
  if(d==N) return dp[a][b][c] = res;

  nx = (double)N / (N-d);

  if(a) res += (solve(a-1,b+1,c)) * a / (a+b+c);
  if(b) res += (solve(a,b-1,c+1)) * b / (a+b+c);
  if(c) res += (solve(a,b,c-1))   * c / (a+b+c);
  res += nx;

  return dp[a][b][c] = res;
}

int main(){
  int i, j, k;
  int a = 0, b = 0, c = 0;
  double res;

  rep(i,120) rep(j,120) rep(k,120) dp[i][j][k] = -1;

  reader(&N);
  rep(i,N) reader(A+i);
  rep(i,N){
    if(A[i]==0) a++;
    if(A[i]==1) b++;
    if(A[i]==2) c++;
  }

  res = solve(a, b, c);

  printf("%.10f\n",res);

  return 0;
}

Current time: 2024年04月24日00時19分32秒
Last modified: 2014年12月24日00時14分25秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：