結果

問題 No.108 トリプルカードコンプ
ユーザー mkreem
提出日時 2024-03-18 22:08:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 14 ms / 5,000 ms
コード長 13,705 bytes
コンパイル時間 3,378 ms
コンパイル使用メモリ 266,112 KB
実行使用メモリ 14,208 KB
最終ジャッジ日時 2024-09-30 05:03:24
合計ジャッジ時間 4,195 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifndef INCLUDED_MAIN
#define INCLUDED_MAIN
#include __FILE__
const ll mod = 998244353; using mint = atcoder::modint998244353;
//const ll mod = 1000000007; using mint = atcoder::modint1000000007;
//------------------------------------------------------------------------------------------------------------------
//------------------------------------------------------------------------------------------------------------------
int main(){
fast();
int n; cin >> n;
int cnt0 = 0, cnt1 = 0, cnt2 = 0;
rep(i, 0, n){
int a; cin >> a;
if(a == 0) cnt0++;
if(a == 1) cnt1++;
if(a == 2) cnt2++;
}
// dp[i][j][k] := 0, 1, 2i, j, k
auto dp = Mvector<3, double>(-1, 109, 109, 109);
dp[0][0][0] = 0; //
auto f = [&](auto f, int i, int j, int k) -> double{
if(dp[i][j][k] != -1) return dp[i][j][k];
double res = 0.0;
res += (double)n/(i+j+k);
if(i) res += (double)i/(i+j+k) * f(f, i-1, j+1, k);
if(j) res += (double)j/(i+j+k) * f(f, i, j-1, k+1);
if(k) res += (double)k/(i+j+k) * f(f, i, j, k-1);
return dp[i][j][k] = res;
};
PREC;
cout << f(f, cnt0, cnt1, cnt2) << newl;
}
#else
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/math>
#include <atcoder/lazysegtree.hpp>
void fast(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
}
using ll = long long;
using ld = long double;
#define newl '\n'
#define INF 1000000039
#define LLINF 393939393939393939
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define PREC std::cout << setprecision(15)
#define PI acos(-1)
#define fore(i, a) for(auto &i : a)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
template <typename T>
int lwb(const std::vector<T>& vec, T x){
return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, T x){
return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
auto max(const T& x){ return *max_element(all(x)); }
template <typename T>
auto min(const T& x){ return *min_element(all(x)); }
template <typename T>
using pq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
//
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b){
if(a < b){ a = b; return 1; }
else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b){
if(a > b){ a = b; return 1; }
else return 0;
}
template <typename T>
void iota(std::vector<T>& vec, bool greater = false){
std::iota(all(vec), 0);
std::sort(all(vec), [&](int i, int j){
if(greater) return vec[i] > vec[j];
return vec[i] < vec[j];
});
}
// pairsecond
template <typename T1, typename T2>
bool cmp(std::pair<T1, T2> a, std::pair<T1, T2> b){
if(a.second != b.second) return a.second < b.second;
else return a.first < b.first;
}
//
template <size_t Dimention, typename T>
class Mvector : public std::vector<Mvector<Dimention-1, T>>{
public:
template <typename N, typename... Sizes>
Mvector(T init, N n, Sizes... sizes) : std::vector<Mvector<Dimention-1, T>>(n, Mvector<Dimention-1, T>(init, sizes...))
{ }
};
template <typename T>
class Mvector<1, T> : public std::vector<T>{
public:
template <typename N>
Mvector(T init, N n) : std::vector<T>(n, init)
{ }
};
// 2vector
template <typename T>
std::vector<T> vmerge(std::vector<T>& a, std::vector<T>& b){
std::vector<T> res;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
return res;
}
//
template <typename T>
class Edge{
public:
int from, to;
T cost;
int ID;
Edge(int to, T cost) : to(to), cost(cost) {} // for WG
Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} // for Edges
Edge(int from, int to, T cost, int ID) : from(from), to(to), cost(cost), ID(ID) {} // for Edges
bool operator<(const Edge<T>& rhs) const { return cost < rhs.cost; };
bool operator>=(const Edge<T>& rhs) const { return !(cost < rhs.cost); };
bool operator>(const Edge<T>& rhs) const { return cost > rhs.cost; };
bool operator<=(const Edge<T>& rhs) const { return !(cost > rhs.cost); };
bool operator==(const Edge<T>& rhs) const { return cost == rhs.cost; };
bool operator!=(const Edge<T>& rhs) const { return !(cost == rhs.cost); };
};
using G = std::vector<std::vector<int>>;
template <typename T>
using WG = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Edges = std::vector<Edge<T>>;
template <typename T, typename F>
// @param ok
// @param ng
// @remark ok > ng ok < ng
T Bsearch(T& ok, T& ng, const F& f){
while(abs(ok-ng) > 1){
T mid = (ok+ng)/2;
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template <typename T, typename F>
T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){
while(itr--){
T mid = (ok+ng)/2;
//T mid = sqrtl(ok*ng);
(f(mid) ? ok : ng) = mid;
}
return ok;
}
template <typename T>
// @brief (k, n-k)-shuffle0, 1, ..., N-1 A
bool next_shuffle(std::vector<T>& vec, int k){
int n = vec.size();
if(n <= k){
return false;
}
// K := L
// N-K := R
auto left = vec.begin();
auto right = vec.begin() + k;
T R_max = *std::max_element(right, vec.end());
T tmp = (std::numeric_limits<T>::min)();
// @param i LR(*i := L_(i))
auto tmpi = left, i = right;
while(tmpi != right){
if(tmp <= *tmpi && *tmpi < R_max){
tmp = *tmpi;
i = tmpi;
}
tmpi++;
}
if(i == right){
return false;
}
// @param j RL_(i)(*j := R_(j))
tmp = (std::numeric_limits<T>::max)();
auto tmpj = right, j = vec.end();
while(tmpj != vec.end()){
if(tmp >= *tmpj && *tmpj > *i){
tmp = *tmpj;
j = tmpj;
}
tmpj++;
}
std::iter_swap(i, j); // L_(i)R_(j)swap
i++, j++;
// L_(i+1)L_(k-1)(:= X)R_(j+1)R_(n-k-1)(:= Y)R_(j+1)
int X_len = k-std::distance(left, i);
int Y_len = n-k-std::distance(right, j);
int swap_len = std::min(X_len, Y_len);
// Xswap_lenYswap_lenswap
std::swap_ranges(right-swap_len, right, j);
if(swap_len == X_len){
std::rotate(j, j+swap_len, vec.end());
}
else{
std::rotate(i, right-swap_len, right);
}
return true;
}
int log2ll(long long N){
int B = -1;
while(N != 0){
B++;
N /= 2;
}
return B;
}
template <typename T>
// @brief (2,...,2)-shuffle0, 1, ..., 2*N-1 A
bool next_pairing(std::vector<T>& vec){
int n = vec.size();
// @param used vec使
ll used = 0;
for(int i = n-1; i >= 0; i--){
used |= (1<<vec[i]);
if(i%2 == 1 && vec[i] < log2ll(used)){ //
vec[i] = __builtin_ctzll(used >> (vec[i]+1)) + vec[i]+1;
used ^= (1<<vec[i]);
for(int j = i+1; j < n; j++){
vec[j] = __builtin_ctzll(used);
used ^= (1<<vec[j]);
}
return true;
}
}
return false;
}
// @brief set
template <typename T>
class RangeSet{
private:
std::set<std::pair<T, T>> s;
T sum; // @param sum RangeSet
T TINF = std::numeric_limits<T>::max()/2;
public:
RangeSet() : sum(T(0)){
s.emplace(TINF, TINF);
s.emplace(-TINF, -TINF);
}
// @brief [l, r]
bool covered(const T l, const T r){
assert(l <= r);
auto itr = std::prev(s.lower_bound({l+1, l+1}));
return ((itr->first <= l) && (r <= itr->second));
}
// @brief x
bool contained(const T x){
auto itr = std::prev(s.lower_bound({x+1, x+1}));
return ((itr->first <= x) && (x <= itr->second));
}
// @brief [l, r][-INF, -INF]
std::pair<T, T> covered_by(const T l, const T r){
assert(l <= r);
auto itr = std::prev(s.lower_bound({l+1, l+1}));
if(itr->first <= l && r <= itr->second) return *itr;
return {-TINF, -TINF};
}
std::pair<T, T> covered_by(const T x){
return covered_by(x, x);
}
// @brief [l, r]
T insert(T l, T r){
assert(l <= r);
auto itr = std::prev(s.lower_bound({l+1, l+1}));
if(itr->first <= l && r <= itr->second) return T(0); // [l, r]
T sum_erased = T(0); // @param sum_erased
if(itr->first <= l && l <= itr->second+1){ // litr
l = itr->first;
sum_erased += itr->second - itr->first + 1;
itr = s.erase(itr);
}
else{ // itr
itr = std::next(itr);
}
while(r > itr->second){
sum_erased += itr->second - itr->first + 1;
itr = s.erase(itr);
}
if(itr->first <= r+1 && r <= itr->second){ // ritr
sum_erased += itr->second - itr->first + 1;
r = itr->second;
s.erase(itr);
}
s.emplace(l, r);
sum += r-l+1-sum_erased;
return r-l+1-sum_erased;
}
T insert(const T x){
return insert(x, x);
}
// @brief [l, r]
T erase(const T l, const T r){
assert(l <= r);
auto itr = std::prev(s.lower_bound({l+1, l+1}));
if(itr->first <= l && r <= itr->second){ // [l, r]1
//
if(itr->first < l) s.emplace(itr->first, l-1);
if(r < itr->second) s.emplace(r+1, itr->second);
s.erase(itr);
sum -= r-l+1;
return r-l+1;
}
T res = T(0);
if(itr->first <= l && l <= itr->second){ // litr
res += itr->second-l+1;
//
if(itr->first < l) s.emplace(itr->first, l-1);
itr = s.erase(itr);
}
else{
itr = std::next(itr);
}
while(itr->second <= r){
res += itr->second - itr->first + 1;
itr = s.erase(itr);
}
if(itr->first <= r && r <= itr->second){ // ritr
res += r-itr->first+1;
//
if(r < itr->second) s.emplace(r+1, itr->second);
s.erase(itr);
}
sum -= res;
return res;
}
T erase(const T x){
return erase(x, x);
}
// @brief
int size() const{
return (int)s.size()-2;
}
/*
x
xx
xx1
*/
T mex(const T x = 0) const{
auto itr = std::prev(s.lower_bound({x+1, x+1}));
if(itr->first <= x && x <= itr->second) return itr->second+1;
else return x;
}
// @brief RangeSet
T sum_all() const{
return sum;
}
// @brief set
std::set<std::pair<T, T>> get() const{
std::set<std::pair<T, T>> res;
for(auto& interval : s) {
if(std::abs(interval.first) == TINF) continue;
res.emplace(interval.first, interval.second);
}
return res;
}
void output() const{
std::cout << "RangeSet:";
for(auto& interval : s){
if(interval.first == -INF || interval.second == INF) continue;
std::cout << "[" << interval.first << "," << interval.second << "]";
}
std::cout << '\n';
}
};
const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const std::vector<std::tuple<int, int, int>> line3{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}};
const std::vector<std::tuple<int, int, int, int>> line4{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15}, {0,4,8,12}, {1,5,9,13}, {2,6,10,14}, {3,7
    ,11,15}, {0,5,10,15}, {3,6,9,12}};
bool OutOfGrid(int i, int j, int h, int w){
if(i < 0 || j < 0 || i >= h || j >= w) return true;
return false;
}
// @brief x^n
ll power(ll x, ll n){
ll res = 1;
while(n){
if(n & 1) res *= x;
x *= x;
n >>= 1;
}
return res;
}
ll power_mod(ll x, ll n, ll m){
ll res = 1;
while(n){
if(n & 1){
res = (res*x) % m;
}
x = (x*x) % m;
n >>= 1;
}
return res;
}
// @brief x/mfloorx/m
ll floor(ll x, ll m){
ll r = (x%m + m) % m; // xm
return (x-r)/m;
}
// @brief x/mceilx/m
ll ceil(ll x, ll m){
return floor(x+m-1, m); // x/m + (m-1)/m
}
using namespace std;
#endif
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0