結果
問題 | No.463 魔法使いのすごろく🎲 |
ユーザー | Kosukekim |
提出日時 | 2020-11-12 04:25:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,418 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 174,356 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 18:57:40 |
合計ジャッジ時間 | 3,016 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 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 | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 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 | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | WA | - |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | AC | 1 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 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); // rep(i,n){ // rep(j,m+1)cout << M[i][j] << " "; // cout << endl; // } 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 n,m;cin >> n >> m; vector<double> c(n); rep(i,n-2) cin >> c[i+1]; Matrix<double> M(n,n); for(int i = n-1;i >= n-m-1;i--) M[i][i] = 1; for(int i = n-m-2;i >= 0;i--){ M[i][i] = 1; for(int j = 1;j <= m;j++){ M[i][i+j] = -double(1)/m; } } // rep(i,n){ // rep(j,n) cout << M[i][j] << " "; // cout << c[i] << endl; // } auto ans = LE(M,c); cout << fixed << setprecision(9) << ans[0] << endl; }