結果

問題 No.108 トリプルカードコンプ
ユーザー hayato fukuoka
提出日時 2022-12-04 13:34:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 3,913 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 168,456 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2024-10-11 12:50:12
合計ジャッジ時間 2,924 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define ll long long
#define repll(i, n) for (ll i = 0; i < n; ++i)
#define rep_upll(i, a, n) for (ll i = a; i < n; ++i)
#define rep_downll(i, a, n) for (ll i = a; i >= n; --i)
#define Pll pair<ll, ll>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rep_up(i, a, n) for (int i = a; i < n; ++i)
#define rep_down(i, a, n) for (int i = a; i >= n; --i)
#define P pair<int, int>

#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define vvvll vector<vector<vector<ll>>>
#define vvll vector<vector<ll>>
#define vll vector<ll>
#define vvvi vector<vector<vector<int>>>
#define vvi vector<vector<int>>
#define vi vector<int>
#define pqll priority_queue<ll>
#define pqllg priority_queue<ll, vector<ll>, greater<ll>>
#define pqi priority_queue<int>
#define pqgi priority_queue<int, vector<int>, greater<int>>
#define pb push_back
#define eb emplace_back

const ll INF = (1ll << 60);
const double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template<typename Tx, typename Ty>Tx dup(Tx x, Ty y){return (x+y-1)/y;}
ll mypow(ll a, ll n) {
    ll ret = 1;
    rep(i, n) {
        if (ret > (ll)(1e18 + 10) / a) return -1;
        ret *= a;
    }
    return ret;
}
ll modpow(ll a, ll n, ll mod){
    if(n == 0) return 1;
    a %= mod;
    if(n % 2) return modpow(a, n-1, mod) * a % mod;
    else return modpow(a*a%mod, n/2, mod);
}
long long modDiv(long long a, long long b, long long m) {
	// Get the value of a/b
	return (a * modpow(b, m - 2, m)) % m;
}

using Graph = vector<vector<long long>>;

/*  PrimeFact
    init(N): 初期化。O(N log log N)
    get(n): クエリ。素因数分解を求める。O(log n)
 */
template <typename T>
struct PrimeFact {
    vector<T> spf;
    PrimeFact(T N) { init(N); }
    void init(T N) { // 前処理。spf を求める
        spf.assign(N + 1, 0);
        for (T i = 0; i <= N; i++) spf[i] = i;
        for (T i = 2; i * i <= N; i++) {
            if (spf[i] == i) {
                for (T j = i * i; j <= N; j += i) {
                    if (spf[j] == j) {
                        spf[j] = i;
                    }
                }
            }
        }
    }
    map<T, T> get(T n) { // nの素因数分解を求める
        map<T, T> m;
        while (n != 1) {
            m[spf[n]]++;
            n /= spf[n];
        }
        return m;
    }
};

template<typename T>
struct BIT {
    int n;
    vector<T> d;
    BIT(int n=0):n(n),d(n+1) {}
    void add(int i, T x=1) {
        for (i++; i <= n; i += i&-i) {
            d[i] += x;
        }
        }
    T sum(int i) {
        T x = 0;
        for (i++; i; i -= i&-i) {
            x += d[i];
        }
        return x;
    }
    T sum(int l, int r) {
        return sum(r-1) - sum(l-1);
    }
};

int n;
double dp[110][110][110] = {};
int cnt[4];

double solve(int x, int y, int z){
    if(dp[x][y][z]!=-1)return dp[x][y][z];
    dp[x][y][z] = 0;
    if(z<n) dp[x][y][z] = (double)z/(n-z);
    if(z<n && x<n) dp[x][y][z] += (solve(x+1, y, z) + 1.0) / (double)(n-z) * (double)(n-x);
    if(z<n && y<x) dp[x][y][z] += (solve(x, y+1, z) + 1.0) / (double)(n-z) * (double)(x-y);
    if(z<n && z<y) dp[x][y][z] += (solve(x, y, z+1) + 1.0) / (double)(n-z) * (double)(y-z);
    return dp[x][y][z];
}

int main(){
    cin >> n;
    rep(i, n+1)rep(j, n+1)rep(k, n+1) dp[i][j][k]=-1;
    dp[n][n][n] = 0;
    rep(i, n){
        int a;
        cin >> a;
        cnt[min(a, 3)]++;
    }
    rep_down(i, 2, 0)cnt[i] += cnt[i+1];
    printf("%.12f\n", solve(cnt[1], cnt[2], cnt[3]));
    // rep(i, n+1)rep(j, n+1)rep(k, n+1)printf("%.12f\n", dp[i][j][k]);
    return 0;
}
0