結果
問題 |
No.108 トリプルカードコンプ
|
ユーザー |
![]() |
提出日時 | 2016-09-27 22:11:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 5,000 ms |
コード長 | 1,531 bytes |
コンパイル時間 | 1,840 ms |
コンパイル使用メモリ | 179,580 KB |
実行使用メモリ | 17,536 KB |
最終ジャッジ日時 | 2024-11-21 07:23:56 |
合計ジャッジ時間 | 3,042 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; namespace { typedef long double real; typedef long long ll; template<class T> ostream& operator<<(ostream& os, const vector<T>& vs) { if (vs.empty()) return os << "[]"; auto i = vs.begin(); os << "[" << *i; for (++i; i != vs.end(); ++i) os << " " << *i; return os << "]"; } template<class T> istream& operator>>(istream& is, vector<T>& vs) { for (auto it = vs.begin(); it != vs.end(); it++) is >> *it; return is; } int N; vector<int> A; void input() { cin >> N; A.resize(N); cin >> A; } map< tuple<int,int,int>, real > cache; real f(int a, int b, int c) { if (a < 0 || b < 0 || c < 0) return 0; real s = a + b + c; if (s == 0) return 0; auto key = make_tuple(a, b, c); if (cache.count(key)) { return cache[key]; } //cerr << a << " " << b << " " << c << " -> " << (N / s) + (a / s * f(a - 1, b + 1, c) + b / s * f(a, b - 1, c + 1) + c / s * f(a, b, c - 1)) << endl; return cache[key] = (N / s) + (a / s * f(a - 1, b + 1, c) + b / s * f(a, b - 1, c + 1) + c / s * f(a, b, c - 1)); } void solve() { vector<int> r(4, 0); for (int i = 0; i < N; i++) { int k = max(0, 3 - A[i]); r[k]++; } cout << fixed << setprecision(12) << f(r[3], r[2], r[1]) << endl; } } int main() { input(); solve(); return 0; }