結果
問題 |
No.65 回数の期待値の練習
|
ユーザー |
![]() |
提出日時 | 2015-07-19 18:59:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,418 bytes |
コンパイル時間 | 1,518 ms |
コンパイル使用メモリ | 167,092 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-08 10:22:35 |
合計ジャッジ時間 | 1,897 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename... Args> class MemoizedRecursion {}; template<typename T> class MemoizedRecursion<T> { protected: vector<bool> use; vector<T> mem; bool used(int v) { if (v >= (int)use.size()) { use.resize(v + 1, false); mem.resize(v + 1); } return use[v]; } T memo(int v) { return mem[v]; } void push(T t, int v) { use[v] = true; mem[v] = t; } virtual T eval(int v) = 0; public: T solve(int v) { if (used(v)) return memo(v); T t = eval(v); push(t, v); return t; } }; template<typename T, typename... Args> class MemoizedRecursion<T, Args...> { protected: map<tuple<Args...>, T> mem; bool used(Args... args) { return mem.count(tie(args...)); } T memo(Args... args) { return mem[tie(args...)]; } void push(T t, Args... args) { mem[tie(args...)] = t; } virtual T eval(Args... args) = 0; public: T solve(Args... args) { if (used(args...)) return memo(args...); T t = eval(args...); push(t, args...); return t; } }; class Dice : public MemoizedRecursion<double> { private: double eval(int v) { double res = 1; for (int i = 1; i <= 6; ++i) { if (v - i > 0) res += solve(v - i) / 6; } return res; } }; int main() { int k; cin >> k; Dice dice; cout << fixed << setprecision(15) << dice.solve(k) << endl; }