結果
問題 | No.75 回数の期待値の問題 |
ユーザー | Kosukekim |
提出日時 | 2020-11-12 03:10:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 6 ms / 5,000 ms |
コード長 | 2,408 bytes |
コンパイル時間 | 1,458 ms |
コンパイル使用メモリ | 173,588 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 18:57:16 |
合計ジャッジ時間 | 2,282 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 4 ms
5,376 KB |
testcase_18 | AC | 5 ms
5,376 KB |
testcase_19 | AC | 6 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> // #include <atcoder/all> // using namespace atcoder; //using mint = modint1000000007; #include <string> #include <vector> #include <algorithm> #define rep(i,n) for (int i = 0;i < (n); ++i) using namespace std; using ll = long long; using P = pair<int,int>; #define chmax(x,y) x = max(x,y) using R=double; using ld = long double; int INF = 2*1e9; ll LINF = 1e18*9; int mod = 1000000007; int mod2 = 1; using graph = vector<vector<int>>; const double eps = 1e-10; template<class T> struct Matrix { vector<vector<T> > val; Matrix(int n, int m, T x = 0) : val(n, vector<T>(m, x)) {} void init(int n, int m, T x = 0) {val.assign(n, vector<T>(m, x));} size_t size() const {return val.size();} inline vector<T>& operator [] (int i) {return val[i];} }; template<class T> int GaussJordan(Matrix<T> &A,bool is_extended = false){ int n = A.size(), m = A[0].size(); int rank = 0; for(int col = 0;col < m;col++){ if(is_extended && col == m-1) break; int pivot = -1; T ma = eps; for(int row = rank;row < n;row++){ if(abs(A[row][col]) > ma){ ma = abs(A[row][col]); pivot = row; } } if(pivot == -1) continue; swap(A[pivot],A[rank]); auto fac = A[rank][col]; for(int col2 = 0;col2 < m;col2++) A[rank][col2] /= fac; for(int row = 0;row < n;row++){ if(row != rank && abs(A[row][col]) > eps){ auto fac = A[row][col]; for(int col2 = 0;col2 < m;col2++){ A[row][col2] -= A[rank][col2]*fac; } } } rank++; } return rank; } template<class T> vector<T> LE(Matrix<T> &A,vector<T> &b){ int n = A.size(),m = A[0].size(); Matrix<T> M(n,m+1); for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++) M[i][j] = A[i][j]; M[i][m] = b[i]; } int rank = GaussJordan(M,true); vector<T> res; for(int row = rank;row < n;row++) if(abs(M[row][m]) > eps) return res; res.assign(m,0); for(int i = 0;i < rank;i++) res[i] = M[i][m]; return res; } int main(){ int k;cin >> k; vector<double> b(k,1); Matrix<double> M(k,k); for(int i = k-1;i >= 0;i--){ M[i][i] = 1; for(int j = 1;j <= 6;j++){ if(i+j==k) continue; if(i+j < k) M[i][i+j] = -double(1)/6; else M[i][0] += -double(1)/6; } } // for(int i = 0;i < k;i++){ // for(int j = 0;j < k;j ++)cout << M[i][j] << " "; // cout << b[i] << endl; // } auto ans = LE(M,b); cout << ans[0] << endl; //for(int i = 0;i < k;i++) cout << ans[i] << endl; }