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

• 問題: No.3674 Zero Sum Game
• ユーザー: 👑 みうね
• 提出日時: 2026-08-22 14:30:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: WA
• 実行時間: -
• コード長: 6,407 bytes
• コンパイル時間: 1,599 ms
• コンパイル使用メモリ: 209,540 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-04 22:34:05
• 合計ジャッジ時間: 111,513 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	AC * 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 = 20000;
    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());

    constexpr int warmup_iterations = 200000;
    std::vector<double> row_sum(n, 0.0);
    std::vector<double> column_sum(m, 0.0);
    std::vector<int> row_count(n, 0);
    int alice = 0;
    int bob = 0;
    for (int iteration = 0; iteration < warmup_iterations; ++iteration) {
        if (iteration != 0) {
            alice = static_cast<int>(
                std::max_element(row_sum.begin(), row_sum.end())
                - row_sum.begin());
            bob = static_cast<int>(
                std::min_element(column_sum.begin(), column_sum.end())
                - column_sum.begin());
        }
        ++row_count[alice];
        for (int i = 0; i < n; ++i) row_sum[i] += a[i][bob];
        for (int j = 0; j < m; ++j) column_sum[j] += a[alice][j];
    }
    std::vector<double> probability(n);
    for (int i = 0; i < n; ++i)
        probability[i] = static_cast<double>(row_count[i]) / warmup_iterations;
    std::vector<double> payoff(m);
    for (int j = 0; j < m; ++j)
        payoff[j] = column_sum[j] / warmup_iterations;

    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);

    auto sample_row = [&]() {
        double position = real01(rng);
        for (int i = 0; i + 1 < n; ++i) {
            position -= probability[i];
            if (position <= 0) return i;
        }
        return n - 1;
    };

    for (int iteration = 0; iteration < iterations; ++iteration) {
        int source;
        int destination;
        if (real01(rng) < 0.9) {
            const int worst_column = static_cast<int>(
                std::min_element(payoff.begin(), payoff.end()) - payoff.begin());

            source = sample_row();
            for (int retry = 0; retry < 7; ++retry) {
                const int row = sample_row();
                if (a[row][worst_column] < a[source][worst_column]) source = row;
            }

            destination = index(rng);
            for (int retry = 0; retry < 15; ++retry) {
                const int row = index(rng);
                if (a[row][worst_column] > a[destination][worst_column])
                    destination = row;
            }
        } else {
            source = sample_row();
            destination = index(rng);
        }
        if (destination == source) destination = (destination + 1) % n;

        const double progress =
            static_cast<double>(iteration) / (iterations - 1);
        auto objective_after_move = [&](double delta) {
            double result = std::numeric_limits<double>::infinity();
            for (int j = 0; j < m; ++j) {
                result = std::min(
                    result,
                    payoff[j] + delta * (a[destination][j] - a[source][j]));
            }
            return result;
        };

        double delta;
        double next;
        const bool line_search = real01(rng) < 0.9;
        if (line_search) {
            double low = 0.0;
            double high = probability[source];
            for (int step = 0; step < 12; ++step) {
                const double left = (2 * low + high) / 3;
                const double right = (low + 2 * high) / 3;
                if (objective_after_move(left) < objective_after_move(right))
                    low = left;
                else
                    high = right;
            }
            delta = (low + high) / 2;
            next = objective_after_move(delta);
            const double endpoint = objective_after_move(probability[source]);
            if (endpoint > next) {
                delta = probability[source];
                next = endpoint;
            }
            if (next <= current) continue;
        } else {
            const double maximum_move = 0.05 * std::pow(2e-6, progress);
            delta = std::min(probability[source], maximum_move) * real01(rng);
            next = objective_after_move(delta);
        }

        const double temperature =
            30.0 * std::pow(1.0 - progress, 3) + 1e-12;
        if (next >= current
            || real01(rng) < std::exp((next - current) / temperature)) {
            for (int j = 0; j < m; ++j) {
                candidate[j] = payoff[j]
                    + delta * (a[destination][j] - a[source][j]);
            }
            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';
    }
}