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

提出ソース

結果

問題	No.75 回数の期待値の問題
ユーザー	nanophoto12
提出日時	2021-05-10 22:19:30
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	20 ms / 5,000 ms
コード長	15,322 bytes
コンパイル時間	4,230 ms
コンパイル使用メモリ	265,104 KB
実行使用メモリ	4,348 KB
最終ジャッジ日時	2023-10-20 06:39:37
合計ジャッジ時間	5,650 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,348 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,348 KB
testcase_03	AC	3 ms 4,348 KB
testcase_04	AC	3 ms 4,348 KB
testcase_05	AC	2 ms 4,348 KB
testcase_06	AC	3 ms 4,348 KB
testcase_07	AC	3 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	3 ms 4,348 KB
testcase_10	AC	3 ms 4,348 KB
testcase_11	AC	3 ms 4,348 KB
testcase_12	AC	3 ms 4,348 KB
testcase_13	AC	3 ms 4,348 KB
testcase_14	AC	3 ms 4,348 KB
testcase_15	AC	3 ms 4,348 KB
testcase_16	AC	10 ms 4,348 KB
testcase_17	AC	16 ms 4,348 KB
testcase_18	AC	19 ms 4,348 KB
testcase_19	AC	20 ms 4,348 KB

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

コンパイルメッセージ

main.cpp:273:9: warning: #pragma once in main file
  273 | #pragma once
      |         ^~~~

ソースコード

raw source code

#include <bits/stdc++.h>

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

template<typename T>
void chmax(T& reference, T value) {
    reference = max(reference, value);
}

template<typename T>
void chmaxmap(map<T, T>& m, T key, T value) {
    if (m.count(key)) {
        chmax(m[key], value);
    }
    else {
        m[key] = value;
    }
}

template<typename T>
void chmin(T& reference, T value) {
    reference = min(reference, value);
}

template< typename G >
struct HeavyLightDecomposition {
    G& g;
    vector< int > sz, in, out, head, rev, par;

    HeavyLightDecomposition(G& g) :
        g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

    void dfs_sz(int idx, int p) {
        par[idx] = p;
        sz[idx] = 1;
        if (g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
        for (auto& to : g[idx]) {
            if (to == p) continue;
            dfs_sz(to, idx);
            sz[idx] += sz[to];
            if (sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
        }
    }

    void dfs_hld(int idx, int par, int& times) {
        in[idx] = times++;
        rev[in[idx]] = idx;
        for (auto& to : g[idx]) {
            if (to == par) continue;
            head[to] = (g[idx][0] == to ? head[idx] : to);
            dfs_hld(to, idx, times);
        }
        out[idx] = times;
    }

    void build() {
        dfs_sz(0, -1);
        int t = 0;
        dfs_hld(0, -1, t);
    }

    int la(int v, int k) {
        while (1) {
            int u = head[v];
            if (in[v] - k >= in[u]) return rev[in[v] - k];
            k -= in[v] - in[u] + 1;
            v = par[u];
        }
    }

    int lca(int u, int v) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) return u;
        }
    }

    template< typename T, typename Q, typename F >
    T query(int u, int v, const T& ti, const Q& q, const F& f, bool edge = false) {
        T l = ti, r = ti;
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v), swap(l, r);
            if (head[u] == head[v]) break;
            l = f(q(in[head[v]], in[v] + 1), l);
        }
        return f(f(q(in[u] + edge, in[v] + 1), l), r);
    }

    template< typename Q >
    void add(int u, int v, const Q& q, bool edge = false) {
        for (;; v = par[head[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (head[u] == head[v]) break;
            q(in[head[v]], in[v] + 1);
        }
        q(in[u] + edge, in[v] + 1);
    }
};

typedef vector<vector<int>> UnWeightedGraph;

class lca {
public:
    typedef vector<vector<int>> Graph;
    const int n;
    const int log2_n;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth;

    lca(const Graph& g, int root)
        : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) {
        dfs(g, root, -1, 0);
        for (int k = 0; k + 1 < log2_n; k++) {
            for (int v = 0; v < (int)g.size(); v++) {
                if (parent[k][v] < 0)
                    parent[k + 1][v] = -1;
                else
                    parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }

    void dfs(const Graph& g, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (int j = 0; j < g[v].size(); j++) {
            if (g[v][j] != p) dfs(g, g[v][j], v, d + 1);
        }
    }

    int get(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int k = 0; k < log2_n; k++) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = log2_n - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[get(u, v)];
    }

};

namespace {
    using namespace std;

    template< typename G >
    struct LowLink {
        const G& g;
        vector< int > used, ord, low;
        vector< int > articulation;
        vector< pair< int, int > > bridge;

        LowLink(const G& g) : g(g) {}

        int dfs(int idx, int k, int par) {
            used[idx] = true;
            ord[idx] = k++;
            low[idx] = ord[idx];
            bool is_articulation = false;
            int cnt = 0;
            for (auto& to : g[idx]) {
                if (!used[to]) {
                    ++cnt;
                    k = dfs(to, k, idx);
                    low[idx] = min(low[idx], low[to]);
                    is_articulation |= ~par && low[to] >= ord[idx];
                    if (ord[idx] < low[to]) bridge.emplace_back(minmax(idx, (int)to));
                }
                else if (to != par) {
                    low[idx] = min(low[idx], ord[to]);
                }
            }
            is_articulation |= par == -1 && cnt > 1;
            if (is_articulation) articulation.push_back(idx);
            return k;
        }

        virtual void build() {
            used.assign(g.size(), 0);
            ord.assign(g.size(), 0);
            low.assign(g.size(), 0);
            int k = 0;
            for (int i = 0; i < g.size(); i++) {
                if (!used[i]) k = dfs(i, k, -1);
            }
        }
    };

    template< typename G >
    struct TwoEdgeConnectedComponents {
        vector< int > comp;
        LowLink< G > lowLink_;
        TwoEdgeConnectedComponents(const G& g) : lowLink_(g) {}

        int operator[](const int& k) {
            return comp[k];
        }

        void dfs(int idx, int par, int& k) {
            if (~par && lowLink_.ord[par] >= lowLink_.low[idx]) comp[idx] = comp[par];
            else comp[idx] = k++;
            for (auto& to : lowLink_.g[idx]) {
                if (comp[to] == -1) dfs(to, idx, k);
            }
        }

        typedef std::vector<std::vector<int>> UnWeightedGraph;

        void build(UnWeightedGraph& t) {
            lowLink_.build();
            comp.assign(lowLink_.g.size(), -1);
            int k = 0;
            for (int i = 0; i < comp.size(); i++) {
                if (comp[i] == -1) dfs(i, -1, k);
            }
            t.resize(k);
            for (auto& e : lowLink_.bridge) {
                int x = comp[e.first], y = comp[e.second];
                t[x].push_back(y);
                t[y].push_back(x);
            }
        }
    };
}

class Primes {
public:
    vector<int> Prime_Number;
    vector<bool> is_prime_;
    Primes(int N) {
        is_prime_.resize(N + 1, true);
        is_prime_[0] = is_prime_[1] = false;
        for (int i = 0; i < N + 1; i++) {
            if (is_prime_[i]) {
                Prime_Number.push_back(i);
                for (int j = 2 * i; j <= N; j += i) is_prime_[j] = false;
            }
        }
    }
    int operator[](int i) { return Prime_Number[i]; }
    int size() { return Prime_Number.size(); }
    int back() { return Prime_Number.back(); }
    bool isPrime(int q) { return is_prime_[q]; }
};

#include <atcoder/all>

using namespace atcoder;

typedef modint1000000007 mint;

#pragma once

#include <vector>

template< class T >
struct Matrix {
    vector< vector< T > > A;

    Matrix() {}

    Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {}

    Matrix(size_t n) : A(n, vector< T >(n, 0)) {};

    size_t height() const {
        return (A.size());
    }

    int size() const {
        return A.size();
    }

    size_t width() const {
        return (A[0].size());
    }

    inline const vector< T >& operator[](int k) const {
        return (A.at(k));
    }

    inline vector< T >& operator[](int k) {
        return (A.at(k));
    }

    static Matrix Identity(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++) mat[i][i] = 1;
        return (mat);
    }

    Matrix& operator+=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] += B[i][j];
        return (*this);
    }

    Matrix& operator-=(const Matrix& B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix& operator*=(const Matrix& B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector< vector< T > > C(n, vector< T >(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix& operator^=(long long k) {
        Matrix B = Matrix::I(height());
        while (k > 0) {
            if (k & 1) B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix& B) const {
        return (Matrix(*this) += B);
    }

    Matrix operator-(const Matrix& B) const {
        return (Matrix(*this) -= B);
    }

    Matrix operator*(const Matrix& B) const {
        return (Matrix(*this) *= B);
    }

    Matrix operator^(const long long k) const {
        return (Matrix(*this) ^= k);
    }

    friend ostream& operator<<(ostream& os, Matrix& p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            os << "[";
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "]\n" : ",");
            }
        }
        return (os);
    }


    T determinant() {
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0) idx = j;
            }
            if (idx == -1) return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};
namespace {
    using namespace std;

    static constexpr double EPS = 0;

    template<class T>
    static int GaussJordan(Matrix<T>& A, bool is_extended = false) {
        int m = A.size(), n = A[0].size();
        int rank = 0;
        for (int col = 0; col < n; ++col) {
            // 拡大係数行列の場合は最後の列は掃き出ししない
            if (is_extended && col == n - 1) break;

            // ピボットを探す
            int pivot = -1;
            T ma = EPS;
            for (int row = rank; row < m; ++row) {
                if (abs(A[row][col]) > ma) {
                    ma = abs(A[row][col]);
                    pivot = row;
                }
            }
            // ピボットがなかったら次の列へ
            if (pivot == -1) continue;

            // まずは行を swap
            swap(A[pivot], A[rank]);

            // ピボットの値を 1 にする
            auto fac = A[rank][col];
            for (int col2 = 0; col2 < n; ++col2) A[rank][col2] /= fac;

            // ピボットのある列の値がすべて 0 になるように掃き出す
            for (int row = 0; row < m; ++row) {
                if (row != rank && abs(A[row][col]) > EPS) {
                    auto fac = A[row][col];
                    for (int col2 = 0; col2 < n; ++col2) {
                        A[row][col2] -= A[rank][col2] * fac;
                    }
                }
            }
            ++rank;
        }
        return rank;
    }

    //誤差に注意
    template<class T>
    static std::vector<T> linear_equation(const Matrix<T>& A, std::vector<T> b) {
        // extended
        int m = A.size(), n = A[0].size();
        Matrix<T> M(m, n + 1);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) M[i][j] = A[i][j];
            M[i][n] = b[i];
        }
        int rank = GaussJordan(M, true);

        // check if it has no solution
        vector<T> res;
        for (int row = rank; row < m; ++row) if (abs(M[row][n]) > EPS) return res;

        // answer
        res.assign(n, 0);
        for (int i = 0; i < rank; ++i) res[i] = M[i][n];
        return res;
    }

    template<typename T>
    void linear_equation_gauss_seidel(
        const Matrix<T>& a, const std::vector<T>& b, std::vector<T>& x,
        int iteration) {
        std::vector<T> buffer = x;
        rep(_, iteration) {
            int rows = a.size();
            int cols = a[0].size();
            for (int y = 0; y < rows; y++) {
                T sum = 0;
                for (int j = 0; j < cols; j++) {
                    if (y != j) {
                        sum += a[y][j] * x[j];
                    }
                }
                T c = (b[y] - sum);
                T next = c / a[y][y];
                buffer[y] = next;
            }
            swap(x, buffer);
        }
    }

    template<typename T>
    void linear_equation_gauss_seidel_sparse(
        const vector<vector<pair<int, T>>>& a, const std::vector<T>& b, std::vector<T>& x,
        int iteration) {
        std::vector<T> buffer = x;
        rep(_, iteration) {
            int rows = a.size();
            int cols = a[0].size();
            for (int y = 0; y < rows; y++) {
                T sum = 0;
                T diag = 0;
                for (auto p : a[y]) {
                    int j = p.first;
                    T value = p.second;
                    if (y != j) {
                        sum += value * x[j];
                    }
                    else {
                        diag = value;
                    }
                }
                T c = (b[y] - sum);
                T next = c / diag;
                buffer[y] = next;
            }
            swap(x, buffer);
        }
    }
}

int main() {
    int k;
    cin >> k;
    vector<double> dp(k + 1, 0);
    vector<double> dp2(k + 1, 0);
    for (int x = 0; x < 10000; x++) {
        dp2.assign(k + 1, 0);
        for (int i = 0; i < k; i++) {
            for (int j = 1; j <= 6; j++) {
                int ij = i + j;
                if (ij > k) {
                    dp2[i] += (dp[0] + 1) / 6;
                }
                else {
                    dp2[i] += (dp[ij] + 1) / 6;
                }
            }
        }
        swap(dp, dp2);
    }
    cout << dp[0] << endl;
    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード