#1175108 (C++23) No.3674 Zero Sum Game

• 問題: No.3674 Zero Sum Game
• ユーザー: 👑 みうね
• 提出日時: 2026-08-06 03:51:54
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 684 ms / 3,000 ms
• コード長: 7,669 bytes
• コンパイル時間: 1,798 ms
• コンパイル使用メモリ: 215,724 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-04 22:07:07
• 合計ジャッジ時間: 27,276 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

#include <iomanip>
#include <iostream>
#include <vector>
// BEGIN expanded instance.hpp

#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

using i64 = std::int64_t;

struct Game {
    int n = 0, m = 0;
    std::vector<std::vector<i64>> a;
};

inline Game generate_game(int n, int m, i64 coefficient_limit, std::uint64_t seed) {
    std::mt19937_64 rng(seed);
    std::uniform_int_distribution<i64> value(-coefficient_limit, coefficient_limit);
    Game g;
    g.n = n; g.m = m;
    g.a.assign(n, std::vector<i64>(m));
    for (auto& row : g.a) for (i64& x : row) x = value(rng);
    return g;
}

inline void print_game(const Game& g, std::ostream& out = std::cout) {
    out << g.n << ' ' << g.m << '\n';
    for (int i = 0; i < g.n; ++i)
        for (int j = 0; j < g.m; ++j)
            out << g.a[i][j] << (j + 1 == g.m ? '\n' : ' ');
}

inline bool read_game(Game& g, std::istream& in = std::cin) {
    if (!(in >> g.n >> g.m)) return false;
    g.a.assign(g.n, std::vector<i64>(g.m));
    for (auto& row : g.a) for (i64& x : row) in >> x;
    return true;
}
// END expanded instance.hpp
// BEGIN expanded lp.hpp

#include <algorithm>
#include <cmath>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <vector>

template <class Real> struct TableauSimplex {
    // A practical absolute tolerance avoids pivoting on round-off noise after
    // a degenerate optimum has effectively been reached.
    static constexpr Real EPS = std::is_same_v<Real, long double> ? 1e-12L : 1e-9;
    int m, n;
    std::vector<int> basis, nonbasis;
    std::vector<std::vector<Real>> d;
    long long pivots = 0;
    long long pivot_limit;

    TableauSimplex(const std::vector<std::vector<Real>>& a,
                   const std::vector<Real>& b, const std::vector<Real>& c,
                   long long limit = 10000000)
        : m((int)b.size()), n((int)c.size()), basis(m), nonbasis(n + 1),
          d(m + 2, std::vector<Real>(n + 2)), pivot_limit(limit) {
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) d[i][j] = a[i][j];
        for (int i = 0; i < m; ++i) basis[i] = n + i, d[i][n] = -1, d[i][n + 1] = b[i];
        for (int j = 0; j < n; ++j) nonbasis[j] = j, d[m][j] = -c[j];
        nonbasis[n] = -1;
        d[m + 1][n] = 1;
    }

    void pivot(int r, int s) {
        if (++pivots > pivot_limit) throw std::runtime_error("simplex pivot limit exceeded");
        const Real inv = 1 / d[r][s];
        for (int i = 0; i < m + 2; ++i) if (i != r)
            for (int j = 0; j < n + 2; ++j) if (j != s)
                d[i][j] -= d[r][j] * d[i][s] * inv;
        for (int j = 0; j < n + 2; ++j) if (j != s) d[r][j] *= inv;
        for (int i = 0; i < m + 2; ++i) if (i != r) d[i][s] *= -inv;
        d[r][s] = inv;
        std::swap(basis[r], nonbasis[s]);
    }

    bool simplex(int phase) {
        const int objective = phase == 1 ? m + 1 : m;
        while (true) {
            int s = -1;
            const bool bland = pivots >= 10000;
            for (int j = 0; j <= n; ++j) {
                if (phase == 2 && nonbasis[j] == -1) continue;
                if (d[objective][j] >= -EPS) continue;
                if (s == -1 || (bland ? nonbasis[j] < nonbasis[s]
                                      : d[objective][j] < d[objective][s] - EPS) ||
                    (!bland && std::abs(d[objective][j] - d[objective][s]) <= EPS && nonbasis[j] < nonbasis[s])) s = j;
            }
            if (s == -1) return true;
            int r = -1;
            for (int i = 0; i < m; ++i) if (d[i][s] > EPS) {
                if (r == -1 || d[i][n + 1] / d[i][s] < d[r][n + 1] / d[r][s] - EPS ||
                    (std::abs(d[i][n + 1] / d[i][s] - d[r][n + 1] / d[r][s]) <= EPS && basis[i] < basis[r])) r = i;
            }
            if (r == -1) return false;
            pivot(r, s);
        }
    }

    // Returns -infinity if infeasible and +infinity if unbounded.
    Real solve(std::vector<Real>& x) {
        int r = 0;
        for (int i = 1; i < m; ++i) if (d[i][n + 1] < d[r][n + 1]) r = i;
        if (d[r][n + 1] < -EPS) {
            pivot(r, n);
            if (!simplex(1) || d[m + 1][n + 1] < -EPS)
                return -std::numeric_limits<Real>::infinity();
            if (std::abs(d[m + 1][n + 1]) > EPS)
                return -std::numeric_limits<Real>::infinity();
            for (int i = 0; i < m; ++i) if (basis[i] == -1) {
                int s = 0;
                for (int j = 1; j <= n; ++j)
                    if (std::abs(d[i][j]) > std::abs(d[i][s])) s = j;
                pivot(i, s);
            }
        }
        if (!simplex(2)) return std::numeric_limits<Real>::infinity();
        x.assign(n, 0);
        for (int i = 0; i < m; ++i) if (basis[i] < n) x[basis[i]] = d[i][n + 1];
        return d[m][n + 1];
    }
};

template <class Real> struct LinearProgram {
    std::vector<std::vector<Real>> a;
    std::vector<Real> b, c;
};
// END expanded lp.hpp
// BEGIN expanded game_lp.hpp

#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>

inline i64 minimum_entry(const Game& g) {
    i64 result = g.a[0][0];
    for (const auto& row : g.a) for (i64 x : row) result = std::min(result, x);
    return result;
}

inline i64 shift_amount(const Game& g) {
    return 1 + std::max<i64>(0, -minimum_entry(g));
}

template <class Real>
LinearProgram<Real> make_shifted_reciprocal_lp(const Game& g, i64 shift) {
    LinearProgram<Real> lp;
    lp.a.assign(g.n, std::vector<Real>(g.m));
    lp.b.assign(g.n, Real(1));
    lp.c.assign(g.m, Real(1));
    for (int i = 0; i < g.n; ++i)
        for (int j = 0; j < g.m; ++j) lp.a[i][j] = Real(g.a[i][j] + shift);
    return lp;
}

// Eliminate p_(N-1)=1-sum_{i<N-1}p_i and write v=min(A)+w.
// Variables are p_0..p_(N-2),w and all right-hand sides are nonnegative.
template <class Real>
LinearProgram<Real> make_direct_game_lp(const Game& g, bool normalize_rows) {
    const i64 low = minimum_entry(g);
    LinearProgram<Real> lp;
    lp.a.assign(g.m + 1, std::vector<Real>(g.n));
    lp.b.assign(g.m + 1, 0);
    lp.c.assign(g.n, 0);
    lp.c[g.n - 1] = 1;
    for (int j = 0; j < g.m; ++j) {
        for (int i = 0; i + 1 < g.n; ++i)
            lp.a[j][i] = -Real(g.a[i][j] - g.a[g.n - 1][j]);
        lp.a[j][g.n - 1] = 1;
        lp.b[j] = Real(g.a[g.n - 1][j] - low);
        if (normalize_rows) {
            auto absolute = [](const Real& x) { return x < 0 ? -x : x; };
            Real scale = std::max<Real>(1, absolute(lp.b[j]));
            for (const Real& x : lp.a[j]) scale = std::max(scale, absolute(x));
            for (Real& x : lp.a[j]) x /= scale;
            lp.b[j] /= scale;
        }
    }
    for (int i = 0; i + 1 < g.n; ++i) lp.a[g.m][i] = 1;
    lp.b[g.m] = 1;
    return lp;
}

inline Game negated_transpose(const Game& g) {
    Game h;
    h.n = g.m; h.m = g.n;
    h.a.assign(h.n, std::vector<i64>(h.m));
    for (int i = 0; i < g.n; ++i)
        for (int j = 0; j < g.m; ++j) h.a[j][i] = -g.a[i][j];
    return h;
}
// END expanded game_lp.hpp

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tests;
    if (!(std::cin >> tests)) return 0;
    for (int test = 0; test < tests; ++test) {
        Game g;
        read_game(g);
        const i64 shift = shift_amount(g);
        auto lp = make_shifted_reciprocal_lp<long double>(g, shift);
        TableauSimplex<long double> solver(lp.a, lp.b, lp.c);
        std::vector<long double> y;
        const long double z = solver.solve(y);
        const long double answer = 1 / z - shift;
        std::cout << std::fixed << std::setprecision(15) << answer << '\n';
    }
}