結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー chocorusk
提出日時 2020-01-01 02:59:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,461 bytes
コンパイル時間 1,366 ms
コンパイル使用メモリ 124,984 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-21 03:24:06
合計ジャッジ時間 2,518 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef double number;
const number eps = 1e-10;
typedef vector<number> arr;
typedef vector<arr> matrix;

// O( n )
matrix identity(int n) {
  matrix A(n, arr(n));
  for (int i = 0; i < n; ++i) A[i][i] = 1;
  return A;
}
// O( n )
number inner_product(const arr &a, const arr &b) {
  number ans = 0;
  for (int i = 0; i < a.size(); ++i)
    ans += a[i] * b[i];
  return ans;
}
// O( n^2 )
arr mul(const matrix &A, const arr &x) {
  arr y(A.size());
  for (int i = 0; i < A.size(); ++i)
    for (int j = 0; j < A[0].size(); ++j)
      y[i] = A[i][j] * x[j];
  return y;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
  matrix C(A.size(), arr(B[0].size()));
  for (int i = 0; i < C.size(); ++i)
    for (int j = 0; j < C[i].size(); ++j)
      for (int k = 0; k < A[i].size(); ++k)
        C[i][j] += A[i][k] * B[k][j];
  return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, int e) {
  return e == 0 ? identity(A.size())  :
     e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1));
}
// O( n^3 )
number det(matrix A) {
  const int n = A.size();
  number D = 1;
  for (int i = 0; i < n; ++i) {
    int pivot = i;
    for (int j = i+1; j < n; ++j)
      if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
    swap(A[pivot], A[i]);
    D *= A[i][i] * (i != pivot ? -1 : 1);
    if (abs(A[i][i]) < eps) break;
    for(int j = i+1; j < n; ++j)
      for(int k = n-1; k >= i; --k)
        A[j][k] -= A[i][k] * A[j][i] / A[i][i];
  }
  return D;
}
// O(n)
number tr(const matrix &A) {
  number ans = 0;
  for (int i = 0; i < A.size(); ++i)
    ans += A[i][i];
  return ans;
}
// O( n^3 ).
int rank(matrix A) {
  const int n = A.size(), m = A[0].size();
  int r = 0;
  for (int i = 0; r < n && i < m; ++i) {
    int pivot = r;
    for (int j = r+1; j < n; ++j)
      if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
    swap(A[pivot], A[r]);
    if (abs(A[r][i]) < eps) continue;
    for (int k = m-1; k >= i; --k)
      A[r][k] /= A[r][i];
    for(int j = r+1; j < n; ++j)
      for(int k = i; k < m; ++k)
        A[j][k] -= A[r][k] * A[j][i];
    ++r;
  }
  return r;
}
struct LUinfo {
  vector<number> value;
  vector<int> index;
};
// O( n^3 ), Gaussian forward elimination
LUinfo LU_decomposition(matrix A) {
  const int n = A.size();
  LUinfo data;
  for (int i = 0; i < n; ++i) {
    int pivot = i;
    for (int j = i+1; j < n; ++j)
      if (abs(A[j][i]) > abs(A[pivot][i])) pivot = j;
    swap(A[pivot], A[i]);
    data.index.push_back(pivot);
    // if A[i][i] == 0, LU decomposition failed.
    for(int j = i+1; j < n; ++j) {
      A[j][i] /= A[i][i];
      for(int k = i+1; k < n; ++k)
        A[j][k] -= A[i][k] * A[j][i];
      data.value.push_back(A[j][i]);
    }
  }
  for(int i = n-1; i >= 0; --i) {
    for(int j = i+1; j < n; ++j)
      data.value.push_back(A[i][j]);
    data.value.push_back(A[i][i]);
  }
  return data;
}
// O( n^2 ) Gaussian backward substitution
arr LU_backsubstitution(const LUinfo &data, arr b) {
  const int n = b.size();
  int k = 0;
  for (int i = 0; i < n; ++i){
    swap(b[data.index[i]], b[i]);
    for(int j = i+1; j < n; ++j)
      b[j] -= b[i] * data.value[k++];
  }
  for (int i = n-1; i >= 0; --i) {
    for (int j = i+1; j < n; ++j)
      b[i] -= b[j] * data.value[k++];
    b[i] /= data.value[k++];
  }
  return b;
}
int main()
{
	int n, m;
	cin>>n>>m;
	double c[101]={};
	for(int i=1; i<n-1; i++){
		cin>>c[i];
	}
	matrix a(n-1, arr(n-1));
	arr b(n-1);
	for(int i=0; i<n-1; i++){
		a[i][i]+=m;
		int k=i+1;
		bool myon=0;
		for(int j=0; j<m; j++){
			b[i]+=c[k];
			if(k<n-1) a[i][k]-=1.0;
			else myon=1;
			if(myon) k--;
			else k++;
		}
	}
	auto sol=LU_backsubstitution(LU_decomposition(a), b);
	double dp[101];
	for(int i=n-m-1; i<n; i++) dp[i]=0;
	for(int i=n-m-2; i>=0; i--){
		dp[i]=0;
		for(int j=1; j<=m; j++) dp[i]+=(dp[i+j]+c[i+j])/m;
		for(int j=1; j<=m; j++){
			dp[i]=min(dp[i], sol[i+j]+c[i+j]);
		}
	}
	printf("%.10lf\n", dp[0]);
	return 0;
}
0