結果
問題 | No.463 魔法使いのすごろく🎲 |
ユーザー |
|
提出日時 | 2016-12-14 02:59:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,420 bytes |
コンパイル時間 | 1,851 ms |
コンパイル使用メモリ | 180,420 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-30 06:58:04 |
合計ジャッジ時間 | 17,784 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 WA * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<class T> ostream &operator <<(ostream &os, const vector<T> &v) { for (T x : v) os << x << " "; return os; } vector<vector<double>> reduce(vector<vector<double>> a) { int h = a.size(); int w = a[0].size(); int r = 0; for (int j = 0; j < w && r < h; j++) { int p = r; for (int i = r + 1; i < h; i++) { if (abs(a[i][j]) > abs(a[p][j])) { p = i; } } swap(a[p], a[r]); if (abs(a[r][j]) < 1e-8) { continue; } for (int ii = 0; ii < h; ii++) { if (ii != r) { double q = a[ii][j] / a[r][j]; for (int jj = 0; jj < w; jj++) { a[ii][jj] -= q * a[r][jj]; } } } double q = a[r][j]; for (int jj = 0; jj < w; jj++) { a[r][jj] /= q; } r++; } return a; } struct SlideMin { deque<pair<double, int>> q; int width; int t = 0; SlideMin(int width) : width(width) {} void add(double x) { t++; while (!q.empty() && t - q.front().second >= width) { q.pop_front(); } while (!q.empty() && q.back().first > x) { q.pop_back(); } q.emplace_back(x, t); } double minimum() { return q.front().first; } }; int main() { int n, m; cin >> n >> m; const int M = n * 2 - 2; vector<double> c(M * 2); for (int i = 1; i < n - 1; i++) { cin >> c[i]; } for (int i = 0; i < n - 2; i++) { c[n + i] = c[n - 2 - i]; } for (int i = 0; i < M; i++) { c[i + M] = c[i]; } const int T = 30000000 / M; double mm = 1.0 / m; vector<vector<double>> a(M - 1, vector<double>(M)); for (int i = 0; i < M; i++) { if (i == n - 1) { continue; } int ii = i > n - 1 ? i - 1 : i; a[ii][ii] = 1; for (int j = 1; j <= m; j++) { int jj = (i + j) % M; if (jj != n - 1) { int jjj = jj > n - 1 ? jj - 1 : jj; a[ii][jjj] -= 1.0 / m; a[ii][M - 1] += c[jj] / m; } else { a[ii][M - 1] += c[jj] / m; } } } a = reduce(a); vector<double> E(M * 2), EE(M * 2); for (int i = 0; i < M; i++) { if (i != n - 1) { int ii = i > n - 1 ? i - 1 : i; E[i] = EE[i] = a[ii][M - 1]; } } SlideMin q(m); for (int i = m - 1; i >= 0; i--) { q.add(EE[i] + c[i]); } double sumE = 0; double sumEE = 0; for (int i = 0; i < m; i++) { sumE += E[i] + c[i]; sumEE += EE[i] + c[i]; } for (int ii = 0; ii < T; ii++) { for (int i = 0; i < M; i++) { E[i + M] = E[i]; EE[i + M] = EE[i]; } for (int i = M - 1; i >= 0; i--) { E[i] = 0; EE[i] = 0; if (i != n - 1) { E[i] = min(sumE * mm, q.minimum()); EE[i] += sumEE * mm; } q.add(EE[i] + c[i]); sumE += E[i] + c[i]; sumEE += EE[i] + c[i]; sumE -= E[i + m] + c[i + m]; sumEE -= EE[i + m] + c[i + m]; } } printf("%.20f\n", (double)min(E[0], EE[0])); }