#239912 (C++17) No.75 回数の期待値の問題

提出ソース

結果

問題	No.75 回数の期待値の問題
ユーザー	Pachicobue
提出日時	2018-02-28 19:25:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	17 ms / 5,000 ms
コード長	8,371 bytes
コンパイル時間	1,023 ms
コンパイル使用メモリ	84,668 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-06-01 09:38:16
合計ジャッジ時間	1,801 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	9 ms 6,940 KB
testcase_18	AC	14 ms 6,940 KB
testcase_19	AC	17 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
using namespace std;
template <typename T>
struct Matrix {
    Matrix(const int n) : Matrix{n, n} {}
    Matrix(const int r, const int c) : R{r}, C{c}, table(r, vector<T>(c, static_cast<T>(0))) {}
    vector<T>& operator[](const int n) { return table[n]; }
    const vector<T>& operator[](const int n) const { return table[n]; }

    Matrix& operator+=(const Matrix& mat)
    {
        assert(R == mat.R and C == mat.C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                table[i][j] += mat[i][j];
            }
        }
        return *this;
    }

    Matrix& operator-=(const Matrix& mat)
    {
        assert(R == mat.R and C == mat.C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                table[i][j] -= mat[i][j];
            }
        }
        return *this;
    }

    Matrix& operator*=(const T val)
    {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                table[i][j] *= val;
            }
        }
        return *this;
    }

    Matrix& operator/=(const T val)
    {
        assert(val != 0);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                table[i][j] /= val;
            }
        }
        return *this;
    }

    Matrix operator-() const
    {
        Matrix result(R, C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                result[i][j] = -table[i][j];
            }
        }
        return result;
    }
    Matrix operator+(const Matrix& mat)
    {
        assert(R == mat.R and C == mat.C);
        Matrix result(R, C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                result[i][j] = table[i][j] + mat[i][j];
            }
        }
        return result;
    }

    Matrix operator-(const Matrix& mat)
    {
        assert(R == mat.R and C == mat.C);
        Matrix result(R, C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                result.table[i][j] = table[i][j] - mat.table[i][j];
            }
        }
        return result;
    }

    Matrix operator*(const T val)
    {
        Matrix result(R, C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                result[i][j] = table[i][j] * val;
            }
        }
        return result;
    }

    Matrix operator*(const Matrix& mat)
    {
        assert(C == mat.R);
        Matrix result(R, mat.C);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < mat.C; j++) {
                T sum = 0;
                for (int k = 0; k < C; k++) {
                    sum += table[i][k] * mat[k][j];
                }
                result[i][j] = sum;
            }
        }
        return result;
    }

    Matrix transposed() const
    {
        Matrix result(C, R);
        for (int i = 0; i < C; i++) {
            for (int j = 0; j < R; j++) {
                result[i][j] = table[j][i];
            }
        }
        return result;
    }
    Matrix& transpose()
    {
        if (R == C) {
            for (int i = 0; i < R; i++) {
                for (int j = i + 1; j < R; j++) {
                    swap(table[i][j], table[j][i]);
                }
            }
            return *this;
        } else {
            return *this = transposed();
        }
    }

    int R;
    int C;
    vector<vector<T>> table;
};

template <typename T>
inline Matrix<T> operator*(const T val, const Matrix<T>& mat)
{
    Matrix<T> result(mat.R, mat.C);
    for (int i = 0; i < mat.R; i++) {
        for (int j = 0; j < mat.C; j++) {
            result[i][j] = val * mat[i][j];
        }
    }
    return result;
}

template <typename T>
inline ostream& operator<<(ostream& os, const Matrix<T>& mat)
{
    os << "Mat<" << mat.R << "," << mat.C << ">" << endl;
    for (int i = 0; i < mat.R; i++) {
        os << "[";
        for (int j = 0; j < mat.C; j++) {
            os << mat[i][j] << ",";
        }
        os << "]" << endl;
    }
    return os;
}
// 縦ベクトル
template <typename T>
struct Vector {
    Vector(const int n) : R(n), table(n, 0){};
    T& operator[](const int n) { return table[n]; }
    const T& operator[](const int n) const { return table[n]; }
    Vector& operator+=(const Vector& v)
    {
        assert(R == v.R);
        for (int i = 0; i < R; i++) {
            table[i] += v[i];
        }
        return *this;
    }
    Vector& operator-=(const Vector& v)
    {
        assert(R == v.R);
        for (int i = 0; i < R; i++) {
            table[i] -= v[i];
        }
        return *this;
    }
    Vector& operator*=(const T& s)
    {
        for (int i = 0; i < R; i++) {
            table[i] *= s;
        }
        return *this;
    }
    Vector& operator/=(const T& s)
    {
        assert(s != 0.0);
        for (int i = 0; i < R; i++) {
            table[i] /= s;
        }
        return *this;
    }
    Vector operator+(const Vector& v) const
    {
        assert(R == v.R);
        Vector result(R);
        for (int i = 0; i < R; i++) {
            result[i] = table[i] + v[i];
        }
        return result;
    }
    Vector operator-(const Vector& v) const
    {
        assert(R == v.R);
        Vector result(R);
        for (int i = 0; i < R; i++) {
            result[i] = table[i] - v[i];
        }
        return result;
    }
    Vector operator*(const T& s) const
    {
        Vector result(R);
        for (int i = 0; i < R; i++) {
            result[i] = table[i] * s;
        }
        return result;
    }
    Vector operator/(const T& s) const
    {
        assert(s != 0.0);
        Vector result(R);
        for (int i = 0; i < R; i++) {
            result[i] = table[i] / s;
        }
        return result;
    }
    Vector operator-() const
    {
        Vector result(R);
        for (int i = 0; i < R; i++) {
            result[i] = -table[i];
        }
        return result;
    }

    int R;
    vector<T> table;
};

template <typename T>
inline Vector<T> operator*(const T& s, const Vector<T>& v)
{
    Vector<T> result(v.R);
    for (int i = 0; i < v.R; i++) {
        result[i] = s * v[i];
    }
    return result;
}

template <typename T>
inline Vector<T> operator*(const Matrix<T>& mat, const Vector<T>& v)
{
    assert(mat.C == v.R);
    Vector<T> result(mat.R);
    for (int i = 0; i < v.R; i++) {
        for (int j = 0; j < mat.R; j++) {
            result[i] += mat[i][j] * v[j];
        }
    }
    return result;
}

template <typename T>
inline ostream& operator<<(ostream& os, const Vector<T>& v)
{
    os << "Vec<" << v.R << ">" << endl;
    os << "[";
    for (int i = 0; i < v.R; i++) {
        os << v[i] << ",";
    }
    os << "]^T" << endl;
    return os;
}


template <typename T>
Vector<T> GaussJordan(const Matrix<T>& mat, const Vector<T>& v)
{
    assert(mat.R == mat.C);
    const int N = mat.R;
    Matrix<T> A(N, N + 1);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = mat[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        A[i][N] = v[i];
    }

    for (int i = 0; i < N; i++) {
        int pivot = i;
        for (int j = i; j < N; j++) {
            if (abs(A[j][i]) > abs(A[pivot][i])) {
                pivot = j;
            }
        }
        assert(A[pivot][i]);
        swap(A[i], A[pivot]);
        for (int j = i + 1; j <= N; j++) {
            A[i][j] /= A[i][i];
        }
        for (int j = 0; j < N; j++) {
            if (i != j) {
                for (int k = i + 1; k <= N; k++) {
                    A[j][k] -= A[j][i] * A[i][k];
                }
            }
        }
    }
    Vector<T> res(N);
    for (int i = 0; i < N; i++) {
        res[i] = A[i][N];
    }
    return res;
}

using ld = long double;

int main()
{
    int K;
    cin >> K;


    Matrix<ld> mat(K + 1, K + 1);
    for (int i = 0; i < K; i++) {
        mat[i][i] = 6;
        for (int j = 1; j <= 6; j++) {
            mat[i][(i + j <= K ? i + j : 0)]--;
        }
    }
    mat[K][K] = 1;
    Vector<ld> vec(K + 1);
    for (int i = 0; i < K; i++) {
        vec[i] = 6;
    }
    vec[K] = 0;
    cout << fixed << setprecision(15) << GaussJordan(mat, vec)[0] << endl;

    return 0;
}

yukicoder

結果

テストケース

ソースコード