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

• 問題: No.3674 Zero Sum Game
• ユーザー: 👑 みうね
• 提出日時: 2026-08-22 14:22:40
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: WA
• 実行時間: -
• コード長: 3,567 bytes
• コンパイル時間: 1,385 ms
• コンパイル使用メモリ: 202,880 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-04 22:31:20
• 合計ジャッジ時間: 23,925 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

using Matrix = std::vector<std::vector<double>>;

double pure_greedy(const Matrix& a, int& best_row) {
    double best = -std::numeric_limits<double>::infinity();
    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        const double value = *std::min_element(a[i].begin(), a[i].end());
        if (value > best) {
            best = value;
            best_row = i;
        }
    }
    return best;
}

// Intentionally incorrect: fixed-iteration simulated annealing has no
// guarantee of reaching the accuracy required by the problem.
double solve(const Matrix& a, std::uint64_t seed) {
    constexpr int iterations = 200000;
    const int n = static_cast<int>(a.size());
    const int m = static_cast<int>(a[0].size());

    if (n == 1) return *std::min_element(a[0].begin(), a[0].end());

    std::vector<double> probability(n, 1.0 / n);
    std::vector<double> payoff(m, 0.0);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            payoff[j] += probability[i] * a[i][j];

    double current = *std::min_element(payoff.begin(), payoff.end());
    double best = current;

    int greedy_row = 0;
    const double greedy_value = pure_greedy(a, greedy_row);
    if (greedy_value > current) {
        std::fill(probability.begin(), probability.end(), 0.0);
        probability[greedy_row] = 1.0;
        payoff = a[greedy_row];
        current = greedy_value;
        best = current;
    }

    std::mt19937_64 rng(seed);
    std::uniform_real_distribution<double> real01(0.0, 1.0);
    std::uniform_int_distribution<int> index(0, n - 1);
    std::vector<double> candidate(m);

    for (int iteration = 0; iteration < iterations; ++iteration) {
        int source = index(rng);
        for (int retry = 0; retry < 20 && probability[source] < 1e-15; ++retry)
            source = index(rng);
        if (probability[source] < 1e-15) continue;

        int destination = index(rng);
        if (destination == source) destination = (destination + 1) % n;

        const double progress =
            static_cast<double>(iteration) / (iterations - 1);
        const double maximum_move = 0.5 * std::pow(2e-7, progress);
        const double delta =
            std::min(probability[source], maximum_move) * real01(rng);

        double next = std::numeric_limits<double>::infinity();
        for (int j = 0; j < m; ++j) {
            candidate[j] = payoff[j]
                + delta * (a[destination][j] - a[source][j]);
            next = std::min(next, candidate[j]);
        }

        const double temperature =
            500.0 * std::pow(1.0 - progress, 3) + 1e-12;
        if (next >= current
            || real01(rng) < std::exp((next - current) / temperature)) {
            probability[source] -= delta;
            probability[destination] += delta;
            payoff.swap(candidate);
            current = next;
            best = std::max(best, current);
        }
    }
    return best;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int tests;
    std::cin >> tests;
    std::cout << std::fixed << std::setprecision(15);
    for (int test = 0; test < tests; ++test) {
        int n, m;
        std::cin >> n >> m;
        Matrix a(n, std::vector<double>(m));
        for (auto& row : a)
            for (double& value : row)
                std::cin >> value;
        std::cout << solve(a, 123456789ULL + test) << '\n';
    }
}