結果

問題 No.108 トリプルカードコンプ
ユーザー okuraofvegetabl
提出日時 2019-09-23 16:19:59
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 2,091 bytes
コンパイル時間 1,293 ms
コンパイル使用メモリ 160,396 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-09-19 04:26:55
合計ジャッジ時間 2,047 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
#define dmp(x) cerr << __LINE__ << " " << #x << " " << x << endl;
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
template<class T,class U>
ostream& operator << (ostream& os,pair<T,U>& p){
  os << p.fi << ',' << p.sec; return os;
}
template<class T,class U>
istream& operator >> (istream& is,pair<T,U>& p){
  is >> p.fi >> p.sec; return is;
}
template<class T>
ostream& operator << (ostream &os,const vector<T> &vec){
  for(int i=0;i<vec.size();i++){
    os << vec[i];
    if(i+1<vec.size())os << ' ';
  }
  return os;
}
template<class T>
istream& operator >> (istream &is,vector<T>& vec){
  for(int i=0;i<vec.size();i++)is >> vec[i];
  return is;
}
void fastio(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(20);
}
int N;
int a[105];
double dp[105][105][105];
double rec(int x,int y,int z){
  if(dp[x][y][z]!=-1.0)return dp[x][y][z];
  auto& t = dp[x][y][z];
  t = 1.0;
  if(N>x+y+z)t += rec(x+1,y,z)*(double)(N-x-y-z)/(double)N;
  if(x>0)t += rec(x-1,y+1,z)*(double)x/(double)N;
  if(y>0)t += rec(x,y-1,z+1)*(double)y/(double)N;
  t /= (1.0-(double)z/(double)N);
  // cout << x << ' ' << y << ' ' << z << ' ' << t << endl;
  return t;
}
int cnt[4];
int main(){
  fastio();
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> a[i];
    cnt[min(a[i],3)]++;
  }
  for(int i=0;i<=100;i++){
    for(int j=0;j<=100;j++){
      for(int k=0;k<=100;k++){
        dp[i][j][k] = -1.0;
      }
    }
  }
  dp[0][0][N] = 0.0;
  cout << rec(cnt[1],cnt[2],cnt[3]) << endl;
  return 0;
}
0