結果
問題 | No.108 トリプルカードコンプ |
ユーザー |
|
提出日時 | 2024-11-29 14:20:54 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 219 ms / 5,000 ms |
コード長 | 8,194 bytes |
コンパイル時間 | 6,960 ms |
コンパイル使用メモリ | 335,412 KB |
実行使用メモリ | 20,352 KB |
最終ジャッジ日時 | 2024-11-29 14:21:03 |
合計ジャッジ時間 | 8,299 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;using ul = unsigned long;using ld = long double;using st = string;using mint = atcoder::modint998244353;using Mint = atcoder::modint1000000007;#define vl vector<ll>#define vvl vector<vector<ll>>#define vvvl vector<vector<vector<ll>>>#define vvvvl vector<vector<vector<vector<ll>>>>#define vd vector<ld>#define vvd vector<vector<ld>>#define vvvd vector<vector<vector<ld>>>#define vb vector<bool>#define vvb vector<vector<bool>>#define vvvb vector<vector<vector<bool>>>#define vs vector<string>#define vvs vector<vector<string>>#define vvvs vector<vector<vector<string>>>#define vp vector<pair<ll,ll>>#define vvp vector<vector<pair<ll,ll>>>#define vvvp vector<vector<vector<pair<ll,ll>>>>#define vm vector<mint>#define vvm vector<vector<mint>>#define vM vector<Mint>#define vvM vector<vector<Mint>>#define cmx(n,v) n=n<v?v:n#define cmn(n,v) n=n>v?v:n#define all(n) begin(n),end(n)#define nxp(a) next_permutation(all(a))#define rev(n) reverse(all(n))#define sor(n) stable_sort(all(n))#define rep(i,n) for(ll i=0;i<(n);++i)#define reprev(i,n) for(ll i=n-1;0<=i;--i)#define rrep(i,a,n) for(ll i=a;i<(n);++i)#define sz(n) n.size()#define bit(j,i) (i&(1<<j))#define yn(x) cout << (x?"Yes":"No") << endl;#define lb(vec,src) lower_bound(vec.begin(),vec.end(),src)-vec.begin()#define ub(vec,src) upper_bound(vec.begin(),vec.end(),src)-vec.begin()#define lb2(vec,src) *lower_bound(vec.begin(),vec.end(),src)#define ub2(vec,src) *upper_bound(vec.begin(),vec.end(),src)#define mne1(a) min_element(all(a))#define mxe1(a) max_element(all(a))#define mne2(a) *min_element(all(a))#define mxe2(a) *max_element(all(a))#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());}const ll inf = 9e18;ll calc_digit(ll N){ll res = 0;while(N>0){res++;N/=10;}return res;}ll factorial(ll n, ll mod = 1e18) {ll ans = 1;for(ll i = n; i >= 2; i--) ans = (ans * i) % mod;return ans;}ll round_up(ll x,ll y){return (x+y-1)/y;}ll floor_int(ll x,ll m){ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換えるreturn (x-r)/m; //return}ll rmd(ll x,ll m){ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換えるreturn r;}ll rmd_2(ll x,ll m){ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換えるreturn (m-r)%m; //return}ll bubble_sort(vl a,ll n){ll res=0;rep(i,n-1){for(ll j=n-1;j>i;j--){if(a[j-1]>a[j]){swap(a[j-1],a[j]);res++;}}}return res;}ll sum_v(vl a){ll res=0;ll n=sz(a);rep(i,n) res+=a[i];return res;}ll stair_sum(ll from,ll to){return (from+to)*(to-from+1)/2;}ll Power(ll var, ll p) {if (p == 1) return var;ll ans = Power(var * var, p / 2);if (p & 1) ans *= var;;return ans;}ll cnt_01(ll n,ll now){ll res=0;res+=(n/now)*(now/2);if(n%now>=now/2) res+=n%now-(now/2)+1;return res;}ll sum_pop(ll n){ll res=0;for(ll b=0;b<60;b++){res+=(n/(1ll<<(b+1)))*(1ll<<b);res+=max(0ll,n%(1ll<<(b+1))-(1ll<<b)+1);}return res;}ll Tree_Diameter(vvl& g){ll n=sz(g);ll start=0;ll ans=0;for(ll i=0;i<2;i++){queue<ll> q;q.push(start);vl dis(n,inf);dis[start]=0;while(!q.empty()){ll u=q.front();q.pop();start=u;ans=dis[u];for(ll v:g[u]){if(dis[v]!=inf) continue;dis[v]=dis[u]+1;q.push(v);}}}return ans;}mint m_Power(mint var,ll p) {if (p == 1) return var;mint ans = m_Power(var * var, p / 2);if (p & 1) ans *= var;;return ans;}Mint M_Power(Mint var,ll p) {if (p == 1) return var;Mint ans = M_Power(var * var, p / 2);if (p & 1) ans *= var;;return ans;}bool is_prime(ll N){if(N==1) return false;if(N==2) return true;if(N%2==0) return false;for(ll p=3;p*p<=N;p+=2) if(N%p==0) return false;return true;}bool in_out(ll x,ll y,ll h,ll w){return 0<=x and x<h and 0<=y and y<w;}bool dis_solve1(ll x1,ll x2,ll y1,ll y2,ll r){ll xx=(x1-x2),yy=(y1-y2);ll dis=xx*xx+yy*yy;return (r*r==dis);}bool dis_solve2(ll x1,ll x2,ll y1,ll y2,ll d1,ll d2){ll xx=(x1-x2),yy=(y1-y2),r1=(d1+d2),r2=(d1-d2);ll dis=xx*xx+yy*yy;return (r2*r2<=dis&&dis<=r1*r1);}void printl(vl v,ll len=0){ll vsz=min(len,ll(v.size()));for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}void prints(vs v){ll vsz=v.size();for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}vl p_list(ll n){vl res;vb check(n+1);for(ll i=2;i<=n;i++){if(check[i]) continue;res.push_back(i);ll ii=i;while(ii<=n){check[ii]=true;ii+=i;}}return res;}vl cumulative_sum(vl a){ll s=sz(a);vl b(s+1,0);for(ll i=0;i<s;i++){b[i+1]=a[i]+b[i];}return b;}vl n_num(ll a,ll n){vl res;while(a){res.push_back(a%n);a/=n;}rev(res);return res;}vl c_press(vl a){ll n=sz(a);vl res=a,c=a;sor(c);uniq(c);rep(i,n) res[i]=lb(c,res[i]);return res;}vl min_fact(ll n){vl pl;vl res(n+1,-1);for(ll d=2;d<=n;d++){if(res[d]==-1){res[d]=d;pl.push_back(d);}for(ll p:pl){if(p*d>n||p>res[d]) break;res[p*d]=p;}}return res;}vvl to_grid(vl &a,ll k){ll n=sz(a);ll m=(n+k-1)/k;vvl b(k,vl(m,inf));rep(i,n) b[i%k][i/k]=a[i];return b;}vvl rotate_ll(vvl& V2d,ll wise){vvl a=V2d;ll h=sz(a),w=sz(a[0]);vvl res(w,vl(h));if(wise) {rep(i,h)rep(j,w) res[j][h-i-1]=a[i][j];}else {rep(i,h)rep(j,w) res[w-j-1][i]=a[i][j];}return res;}vs rotate_st(vs s,ll wise){vs a=s;ll h=sz(a),w=sz(a[0]);vs res(w);rep(i,w) res[i].append(h,'.');if(wise) {rep(i,h)rep(j,w) res[j][h-i-1]=a[i][j];}else {rep(i,h)rep(j,w) res[w-j-1][i]=a[i][j];}return res;}vp prime_factorize(ll N){vp res;for (ll a = 2; a * a <= N; ++a) {if (N % a != 0) continue;ll ex = 0;while (N % a == 0) {ex++;N /= a;}res.push_back({a, ex});}if (N != 1) res.push_back({N, 1});return res;}template <typename T> void input(T &a) { cin >> a; };template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };template<typename T = ll>vector<T> rd(size_t n) {vector<T> ts(n);for (size_t i = 0; i < n; i++) cin >> ts[i];return ts;}template<typename TV, const ll N> void read_tuple_impl(TV&) {}template<typename TV, const ll N, typename Head, typename... Tail>void read_tuple_impl(TV& ts) {get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));read_tuple_impl<TV, N + 1, Tail...>(ts);}template<typename... Ts> decltype(auto) read_tuple(size_t n) {tuple<vector<Ts>...> ts;for (size_t i = 0; i < n; i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);return ts;}ll di[8]={1,-1,0,0,1,1,-1,-1};ll dj[8]={0,0,1,-1,1,-1,-1,1};//abcdefghijklmnopqrstuvwxyz//std::setprecision(15);//2^29<10^9int main(){ios::sync_with_stdio(0);cin.tie(0);ll n;cin >> n;vl a=rd(n);vl cnt(3);rep(i,n){if(a[i]>=3) continue;cnt[a[i]]++;}map<array<ll,3>,ld> dp;dp[{0,0,0}]=0.0;auto e = [&] (auto f,ll i,ll j,ll k) -> ld {if(dp.count({i,j,k})) return dp[{i,j,k}];ld res=ld(n)/ld(i+j+k);if(i>0) res+=f(f,i-1,j+1,k)*(ld(i)/ld(i+j+k));if(j>0) res+=f(f,i,j-1,k+1)*(ld(j)/ld(i+j+k));if(k>0) res+=f(f,i,j,k-1)*(ld(k)/ld(i+j+k));return dp[{i,j,k}]=res;};ld ans=e(e,cnt[0],cnt[1],cnt[2]);cout << setprecision(15) << ans << endl;return 0;}