#1195013 (C++23(gcc16)) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: 炭素(breso)
• 提出日時: 2026-10-24 15:52:00
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,866 ms / 2,000 ms
• コード長: 6,731 bytes
• コンパイル時間: 3,841 ms
• コンパイル使用メモリ: 369,420 KB
• 実行使用メモリ: 17,824 KB
• スコア: 149,257,628
• 最終ジャッジ日時: 2026-10-24 15:54:36
• 合計ジャッジ時間: 155,363 ms
• ジャッジサーバーID （参考情報）: judge6_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

#include <bits/stdc++.h>
using namespace std;

constexpr int SAMPLE_COUNT = 1000;
constexpr double TIME_LIMIT = 1.9;
constexpr double START_TEMP = 100000.0;
constexpr double END_TEMP = 1.0;

struct Problem {
    int n, k;
    vector<int> dryness, trees;

    void read(istream& in) {
        in >> n >> k;
        dryness.resize(n * n);
        for (int i = 0; i < n; ++i) {
            string row;
            in >> row;
            for (int j = 0; j < n; ++j) {
                int v = i * n + j;
                dryness[v] = row[j] - '0';
                if (dryness[v] > 0) trees.push_back(v);
            }
        }
    }
};

struct State {
    vector<int> cut, uncut;
    vector<uint8_t> is_cut;
};

State initial_state(const Problem& p, mt19937& rng) {
    State s;
    s.is_cut.assign(p.n * p.n, false);
    vector<int> remaining;
    for (int v : p.trees) {
        if (v / p.n == 25 || v % p.n == 25) {
            s.cut.push_back(v);
            s.is_cut[v] = true;
        } else {
            remaining.push_back(v);
        }
    }
    if (s.cut.size() > static_cast<size_t>(p.k)) {
        throw runtime_error("The specified initial cuts exceed K");
    }
    shuffle(remaining.begin(), remaining.end(), rng);
    for (int v : remaining) {
        if (s.cut.size() < static_cast<size_t>(p.k)) {
            s.cut.push_back(v);
            s.is_cut[v] = true;
        } else {
            s.uncut.push_back(v);
        }
    }
    return s;
}

struct UnionFind {
    vector<int> parent;

    explicit UnionFind(int size) : parent(size, -1) {}

    int root(int v) {
        int r = v;
        while (parent[r] >= 0) r = parent[r];
        while (v != r) {
            int next = parent[v];
            parent[v] = r;
            v = next;
        }
        return r;
    }

    void unite(int a, int b) {
        a = root(a);
        b = root(b);
        if (a == b) return;
        if (parent[a] > parent[b]) swap(a, b);
        parent[a] += parent[b];
        parent[b] = a;
    }
};

struct Evaluator {
    int n, cells;
    vector<uint8_t> dry;
    vector<int> lightning;
    // Dry-to-dry edges are fixed across all evaluations.
    vector<pair<uint16_t, uint16_t>> edges;
    vector<size_t> edge_begin;
    UnionFind uf;

    Evaluator(const Problem& p, mt19937& rng, int samples = SAMPLE_COUNT)
        : n(p.n), cells(n * n), dry(size_t(samples) * cells),
          lightning(samples), edge_begin(samples + 1), uf(cells) {
        edges.reserve(size_t(samples) * cells / 2);
        uniform_int_distribution<int> tenth(0, 9);
        uniform_int_distribution<int> cell(0, cells - 1);
        for (int a = 0; a < samples; ++a) {
            for (int v = 0; v < cells; ++v) {
                dry[size_t(a) * cells + v] = tenth(rng) < p.dryness[v];
            }
            lightning[a] = cell(rng);
            edge_begin[a] = edges.size();
            const uint8_t* d = dry.data() + size_t(a) * cells;
            if (d[lightning[a]]) {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        int v = i * n + j;
                        if (!d[v]) continue;
                        if (i > 0 && d[v - n]) edges.emplace_back(v, v - n);
                        if (j > 0 && d[v - 1]) edges.emplace_back(v, v - 1);
                    }
                }
            }
        }
        edge_begin[samples] = edges.size();
    }

    // Total burned trees over the fixed samples: lower is better.
    // -1 means the deadline was reached before all samples were evaluated.
    int64_t evaluate(const vector<uint8_t>& cut,
                     chrono::steady_clock::time_point deadline =
                         chrono::steady_clock::time_point::max()) {
        int64_t total = 0;
        for (size_t a = 0; a < lightning.size(); ++a) {
            if ((a & 31) == 0 && chrono::steady_clock::now() >= deadline) return -1;
            const uint8_t* d = dry.data() + a * cells;
            const int hit = lightning[a];
            if (cut[hit] || !d[hit]) continue;
            fill(uf.parent.begin(), uf.parent.end(), -1);
            for (size_t e = edge_begin[a]; e < edge_begin[a + 1]; ++e) {
                auto [u, v] = edges[e];
                if (!cut[u] && !cut[v]) uf.unite(u, v);
            }
            total -= uf.parent[uf.root(hit)];
        }
        return total;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const auto start = chrono::steady_clock::now();
    const auto deadline = start + chrono::duration_cast<chrono::steady_clock::duration>(
                                      chrono::duration<double>(TIME_LIMIT));
    Problem p;
    p.read(cin);
    mt19937 rng(283);
    State state = initial_state(p, rng);
    Evaluator evaluator(p, rng);
    int64_t current_score = evaluator.evaluate(state.is_cut);
    int64_t best_score = current_score;
    vector<int> best_cut = state.cut;
    uniform_real_distribution<double> unit(0.0, 1.0);
    int64_t iterations = 0;

    while (!state.cut.empty() && !state.uncut.empty()) {
        const auto now = chrono::steady_clock::now();
        if (now >= deadline) break;
        const double progress = chrono::duration<double>(now - start).count() / TIME_LIMIT;
        const double temperature = START_TEMP * pow(END_TEMP / START_TEMP, progress);
        const int ci = uniform_int_distribution<int>(0, int(state.cut.size()) - 1)(rng);
        const int ui = uniform_int_distribution<int>(0, int(state.uncut.size()) - 1)(rng);
        const int old_cut = state.cut[ci];
        const int new_cut = state.uncut[ui];
        state.is_cut[old_cut] = false;
        state.is_cut[new_cut] = true;
        const int64_t next_score = evaluator.evaluate(state.is_cut, deadline);
        if (next_score < 0) {
            state.is_cut[old_cut] = true;
            state.is_cut[new_cut] = false;
            break;
        }
        ++iterations;
        const int64_t delta = next_score - current_score;
        if (delta <= 0 || unit(rng) < exp(-double(delta) / temperature)) {
            swap(state.cut[ci], state.uncut[ui]);
            current_score = next_score;
            if (current_score < best_score) {
                best_score = current_score;
                best_cut = state.cut;
            }
        } else {
            state.is_cut[old_cut] = true;
            state.is_cut[new_cut] = false;
        }
    }

    cout << best_cut.size() << '\n';
    for (int v : best_cut) cout << v / p.n << ' ' << v % p.n << '\n';
    cerr << "iterations=" << iterations << " best_burn_total=" << best_score
         << " elapsed=" << chrono::duration<double>(chrono::steady_clock::now() - start).count()
         << '\n';
    return 0;
}