結果

問題 No.463 魔法使いのすごろく🎲
コンテスト
ユーザー kazuma
提出日時 2018-12-28 15:02:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 5,566 bytes
コンパイル時間 2,251 ms
コンパイル使用メモリ 205,260 KB
最終ジャッジ日時 2025-01-06 20:05:49
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

template<class T>
class matrix {
	vector<vector<T>> dat;
public:
	matrix(int row) : dat(row, vector<T>(1)) {}
	matrix(int row, int col) : dat(row, vector<T>(col)) {}
	matrix(int row, int col, const T& id) : dat(row, vector<T>(col, id)) {}
	matrix(const vector<vector<T>>& v) : dat(v) {}
	matrix(const vector<T>& v) : dat(v.size(), vector<T>(1)) {
		for (int i = 0; i < (int)v.size(); ++i) dat[i][0] = v[i];
	}
	explicit operator vector<vector<T>>() const { return dat; }
	int row_size() const { return dat.size(); }
	int col_size() const { return dat[0].size(); }
	matrix<T>& operator+=(const matrix<T>& that) {
		int row = row_size(), col = col_size();
		assert(row_size() == that.row_size() && col_size() == that.col_size());
		for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) dat[i][j] += that[i][j];
		return *this;
	}
	matrix<T>& operator-=(const matrix<T>& that) {
		int row = row_size(), col = col_size();
		assert(row_size() == that.row_size() && col_size() == that.col_size());
		for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) dat[i][j] -= that[i][j];
		return *this;
	}
	matrix<T>& operator*=(const T& that) {
		int row = row_size(), col = col_size();
		for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) dat[i][j] *= that;
		return *this;
	}
	matrix<T>& operator/=(const T& that) {
		int row = row_size(), col = col_size();
		for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) dat[i][j] /= that;
		return *this;
	}
	matrix<T> operator*(const matrix<T>& that) const {
		int x = row_size(), y = col_size(), z = that.col_size();
		assert(col_size() == that.row_size());
		matrix<T> res(x, z);
		for (int i = 0; i < x; ++i) {
			for (int j = 0; j < y; ++j) {
				for (int k = 0; k < z; ++k) {
					res[i][k] += dat[i][j] * that[j][k];
				}
			}
		}
		return res;
	}
	matrix<T>& operator*=(const matrix<T>& that) { return *this = *this * that; }

	vector<T>& operator[](size_t i) & { return dat[i]; }
	const vector<T>& operator[](size_t i) const& { return dat[i]; }
	vector<T> operator[](size_t i) const&& { return move(dat[i]); }

	T& get(int i, int j) & {
		assert(0 <= i && i < row_size());
		assert(0 <= j && j < col_size());
		return dat[i][j];
	}
	const T& get(int i, int j) const& {
		assert(0 <= i && i < row_size());
		assert(0 <= j && j < col_size());
		return dat[i][j];
	}
	T get(int i, int j) const&& {
		assert(0 <= i && i < row_size());
		assert(0 <= j && j < col_size());
		return move(dat[i][j]);
	}
	matrix<T> transpose() const {
		int row = row_size(), col = col_size();
		matrix<T> res(col, row);
		for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) res[j][i] = dat[i][j];
		return res;
	}
};

template <class T> matrix<T> operator+(const matrix<T>& a, const matrix<T>& b) { return matrix<T>(a) += b; }
template <class T> matrix<T> operator-(const matrix<T>& a, const matrix<T>& b) { return matrix<T>(a) -= b; }
template <class T> matrix<T> operator*(const matrix<T>& a, const T& b) { return matrix<T>(a) *= b; }
template <class T> matrix<T> operator*(const T& a, const matrix<T>& b) { return matrix<T>(b) *= a; }
template <class T> matrix<T> operator/(const matrix<T>& a, const T& b) { return matrix<T>(a) /= b; }

template <class T> matrix<T> identity_matrix(int n) {
	matrix<T> a(n, n);
	for (int i = 0; i < n; i++) a[i][i] = T(1);
	return a;
}

template <class T> matrix<T> pow(const matrix<T>& a, long long b) {
	const int n = a.row_size();
	assert(a.row_size() == a.col_size() && 0 <= b);
	matrix<T> res = identity_matrix<T>(n), x(a);
	while (true) {
		if (b & 1LL) res *= x;
		if (!(b >>= 1LL)) break;
		x *= x;
	}
	return res;
}

const ld eps = 1e-10;

template <typename T>
bool is_zero(T val) {
	return val == T(0);
}

template <>
bool is_zero(ld val) {
	return std::abs(val) < eps;
}

template <typename T>
vector<T> gauss_jordan(const matrix<T>& A, const vector<T>& b) {
	const int n = A.row_size();
	matrix<T> B(n, n + 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) B[i][j] = A[i][j];
		B[i][n] = b[i];
	}
	for (int i = 0; i < n; ++i) {
		int pivot = i;
		for (int j = i; j < n; ++j) {
			if (std::abs(B[j][i]) > std::abs(B[pivot][i])) pivot = j;
			if (!is_zero(B[j][i])) pivot = j;
		}
		if (i != pivot) swap(B[i], B[pivot]);
		if (is_zero(B[i][i])) return vector<T>(); // no solution
		for (int j = i + 1; j <= n; ++j) B[i][j] /= B[i][i];
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			for (int k = i + 1; k <= n; ++k) B[j][k] -= B[j][i] * B[i][k];
		}
	}
	vector<T> x(n);
	for (int i = 0; i < n; ++i) x[i] = B[i][n];
	return x;
}

int main()
{
	cout << fixed << setprecision(10);
	int n, m;
	cin >> n >> m;
	vector<int> c(n);
	for (int i = 1; i < n - 1; i++) {
		cin >> c[i];
	}
	reverse(c.begin(), c.end());
	matrix<ld> mat(m, m);
	vector<ld> b(m);
	mat[0][0] = 1; b[0] = 0;
	for (int i = 1; i < m; i++) {
		mat[i][i] = -1;
		int x = m - (i * 2 <= m);
		b[i] += (ld)-c[i] * m / x;
		for (int j = 1; j <= m; j++) {
			int p = abs(i - j);
			if (p == i) continue;
			mat[i][p] += (ld)1 / x;
		}
	}
	vector<ld> dp1 = gauss_jordan(mat, b);
	assert(!dp1.empty());
	vector<vector<ld>> dp(2, vector<ld>(n));
	for (int i = 1; i < n; i++) {
		if (i < m) {
			dp[0][i] = dp1[i];
			dp[1][i] = c[i];
		}
		else {
			for (int j = 1; j <= m; j++) {
				dp[0][i] += (dp[0][i - j] + c[i]) / m;
				dp[1][i] += (dp[1][i - j] + c[i]) / m;
			}
			for (int j = 1; j <= m; j++) {
				dp[1][i] = min(dp[1][i], dp[0][i - j] + c[i]);
			}
		}
	}
	cout << dp[1][n - 1] << endl;
	return 0;
}
0