結果
問題 |
No.463 魔法使いのすごろく🎲
|
ユーザー |
![]() |
提出日時 | 2025-06-20 18:09:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,649 bytes |
コンパイル時間 | 1,538 ms |
コンパイル使用メモリ | 159,772 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 18:09:30 |
合計ジャッジ時間 | 2,941 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long const int NN = 105; const double eps = 1e-12; int n, m; double c[NN]; double cost[NN]; double g[NN], G[NN], M[NN]; double A[NN][NN], rhs[NN], h[NN]; inline int ne(int x, int k) { if (n == 1) return 1; if (n == 2) return ((x - 1 + k) & 1) + 1; int len = n - 1; int q = (x - 1 + k) % (2 * len); return (q < len) ? (q + 1) : (2 * len - q + 1); } void gauss(int N, double A[][NN], double b[], double x[]) { for (int i = 0; i < N; i ++ ) { int piv = i; for (int r = i + 1; r < N; r ++ ) if (fabs(A[r][i]) > fabs(A[piv][i])) piv = r; if (piv != i) { for (int c = i; c < N; c ++ ) swap(A[i][c], A[piv][c]); swap(b[i], b[piv]); } double div = A[i][i]; for (int c = i; c < N; c ++ ) A[i][c] /= div; b[i] /= div; for (int r = 0; r < N; r ++ ) if (r != i && fabs(A[r][i]) > 0) { double mul = A[r][i]; for (int c = i; c < N; c ++ ) A[r][c] -= mul * A[i][c]; b[r] -= mul * b[i]; } } for (int i = 0; i < N; i ++ ) x[i] = b[i]; } signed main() { cin >> n >> m; for (int i = 2; i < n; i ++ ) cin >> c[i]; c[1] = c[n] = 0; for (int i = 1; i <= n; i ++ ) cost[i] = c[i]; int N = n - 1; for (int i = 0; i < N; i ++ ) { for (int j = 0; j < N; j ++ ) A[i][j] = 0; A[i][i] = 1; double SS = 0; int x = i + 1; for (int k = 1; k <= m; k ++ ) { int y = ne(x, k); SS += cost[y] / m; if (y != n) A[i][y - 1] -= 1.0 / m; } rhs[i] = SS; } gauss(N, A, rhs, h); h[n - 1] = 0; for (int x = 1; x < n; x ++ ) { double res = 1e18; for (int k = 1; k <= m; k ++ ) { int y = ne(x, k); double v = cost[y] + (y == n ? 0 : h[y - 1]); res = min(res, v); } M[x] = res; } for (int x = 1; x <= n; x ++ ) g[x] = (x < n ? M[x] : 0); while (1) { double diff = 0; for (int x = 1; x < n; x ++ ) { double R = 0; for (int k = 1; k <= m; k ++ ) { int y = ne(x, k); R += (cost[y] + g[y]) / m; } G[x] = min(R, M[x]); diff = max(diff, fabs(G[x] - g[x])); } for (int x = 1; x < n; x ++ ) g[x] = G[x]; if (diff < eps) break; } cout << fixed << setprecision(10) << g[1]; return 0; }