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

• 問題: No.5025 Forest Fire
• ユーザー: prussian_coder
• 提出日時: 2026-10-24 16:58:13
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,793 ms / 2,000 ms
• コード長: 8,025 bytes
• コンパイル時間: 2,389 ms
• コンパイル使用メモリ: 266,248 KB
• 実行使用メモリ: 9,924 KB
• スコア: 163,609,998
• 最終ジャッジ日時: 2026-10-24 17:03:23
• 合計ジャッジ時間: 149,374 ms
• ジャッジサーバーID （参考情報）: judge6_0 / <nil>

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

ソースコード

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <limits>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using Connection = pair<int, int>;

constexpr int SAFE_ZONE_CRITERIA = 5;
constexpr int CAND_SIZES_LIM = 10000;
constexpr double TIME_LIMIT = 1.8;
constexpr double START_TEMP = 10000;
constexpr double END_TEMP = 10;
constexpr double TWO_ADD_ONE_REMOVE_PROB = 0.3;
constexpr double TWO_REMOVE_ONE_ADD_PROB = 0.3;

int N, K, N2;
vector<vector<int>> board;
vector<int> danger_zones;

int to_1d(int i, int j) { return i * N2 + j; }
pair<int, int> to_2d(int v) { return {v / N2, v % N2}; }

int connection_dist(int v1, int v2) {
    auto [x1, y1] = to_2d(v1);
    auto [x2, y2] = to_2d(v2);
    return min(abs(x1 - x2), abs(y1 - y2));
}

int connection_dist(Connection edge) {
    return connection_dist(edge.first, edge.second);
}

vector<int> create_route(int v1, int v2) {
    auto [x1, y1] = to_2d(v1);
    auto [x2, y2] = to_2d(v2);
    if (x1 > x2) {
        swap(x1, x2);
        swap(y1, y2);
    }
    vector<int> route;
    int x = x1, y = y1;
    while (x != x2 || y != y2) {
        if (x < x2) ++x;
        if (y < y2) ++y;
        else if (y > y2) --y;
        if (x != x2 || y != y2) route.push_back(to_1d(x, y));
    }
    return route;
}

struct UnionFind {
    vector<int> parents;
    explicit UnionFind(int n) : parents(n, -1) {}
    int find(int x) {
        if (parents[x] < 0) return x;
        return parents[x] = find(parents[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (parents[x] > parents[y]) swap(x, y);
        parents[x] += parents[y];
        parents[y] = x;
    }
};

vector<int> build_trees(const vector<Connection>& connections) {
    vector<int> trees;
    vector<bool> used(N2 * N2, false);
    for (auto it = connections.rbegin(); it != connections.rend(); ++it) {
        for (int v : create_route(it->first, it->second)) {
            if (used[v]) continue;
            auto [x, y] = to_2d(v);
            if (board[x][y] == 0) continue;
            used[v] = true;
            trees.push_back(v);
            if (static_cast<int>(trees.size()) == K) return trees;
        }
    }
    return trees;
}

long long evalulate(const vector<int>& trees) {
    vector<bool> removed(N2 * N2, false);
    for (int v : trees) removed[v] = true;
    vector<int> targets, targets_idx(N2 * N2, -1);
    for (int v : danger_zones) {
        if (removed[v]) continue;
        targets_idx[v] = static_cast<int>(targets.size());
        targets.push_back(v);
    }
    UnionFind uf(static_cast<int>(targets.size()));
    for (int v : targets) {
        for (int d : {1, -1, N2, -N2}) {
            int neighbor = v + d;
            if (neighbor < 0 || neighbor >= N2 * N2 || targets_idx[neighbor] < 0) continue;
            uf.unite(targets_idx[v], targets_idx[neighbor]);
        }
    }
    long long score = 0;
    for (int size : uf.parents) {
        if (size < 0) score += 1LL * size * size;
    }
    return score;
}

int main() {
    const auto start_time = chrono::steady_clock::now();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> N >> K)) return 0;
    N2 = N + 2;
    board.assign(N2, vector<int>(N2, 0));
    for (int i = 0; i < N; ++i) {
        string row;
        cin >> row;
        for (int j = 0; j < N; ++j) board[i + 1][j + 1] = row[j] - '0';
    }
    mt19937 rng(random_device{}());
    auto randint = [&](int lo, int hi) {
        return uniform_int_distribution<int>(lo, hi)(rng);
    };
    auto random_real = [&]() {
        return uniform_real_distribution<double>(0.0, 1.0)(rng);
    };
    vector<int> safe_zones;
    for (int i = 0; i < N2; ++i) {
        for (int j = 0; j < N2; ++j) {
            if (board[i][j] <= SAFE_ZONE_CRITERIA) safe_zones.push_back(to_1d(i, j));
            else danger_zones.push_back(to_1d(i, j));
        }
    }
    set<Connection> candidate_set;
    while (candidate_set.size() <= CAND_SIZES_LIM) {
        int v1 = safe_zones[randint(0, static_cast<int>(safe_zones.size()) - 1)];
        int v2 = safe_zones[randint(0, static_cast<int>(safe_zones.size()) - 1)];
        int dist = connection_dist(v1, v2);
        if (2 <= dist && dist <= 16) candidate_set.emplace(v1, v2);
    }
    vector<Connection> edge_candidates(candidate_set.begin(), candidate_set.end());
    vector<Connection> connections;
    vector<int> edges, best_trees;
    int est_sizes = 0;
    double current_score = numeric_limits<double>::infinity();
    long long best_score = numeric_limits<long long>::max();
    auto contains_edge = [&](int edge) {
        return find(edges.begin(), edges.end(), edge) != edges.end();
    };

    while (true) {
        double elapsed = chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
        if (elapsed > TIME_LIMIT) break;
        double temperature = START_TEMP + (END_TEMP - START_TEMP) * elapsed / TIME_LIMIT;
        int x = randint(0, CAND_SIZES_LIM);
        double r = random_real();
        if (contains_edge(x)) continue;
        auto prev_edges = edges;
        auto prev_connections = connections;
        int prev_est_sizes = est_sizes;
        double move_r = est_sizes > 90 ? random_real() : 0.0;
        if (est_sizes <= 90) {
            connections.push_back(edge_candidates[x]);
            est_sizes += connection_dist(edge_candidates[x]);
            edges.push_back(x);
        } else if (move_r < TWO_ADD_ONE_REMOVE_PROB && est_sizes < 105) {
            if (edge_candidates.size() - edges.size() < 2) continue;
            int z = randint(0, CAND_SIZES_LIM);
            while (z == x || contains_edge(z)) z = randint(0, CAND_SIZES_LIM);
            int y = randint(0, static_cast<int>(edges.size()) - 1);
            est_sizes -= connection_dist(connections[y]);
            connections.erase(connections.begin() + y);
            edges.erase(edges.begin() + y);
            for (int new_edge : {x, z}) {
                edges.push_back(new_edge);
                connections.push_back(edge_candidates[new_edge]);
                est_sizes += connection_dist(edge_candidates[new_edge]);
            }
        } else if (TWO_ADD_ONE_REMOVE_PROB <= move_r &&
                   move_r < TWO_ADD_ONE_REMOVE_PROB + TWO_REMOVE_ONE_ADD_PROB) {
            if (edges.size() < 2) continue;
            int y1 = randint(0, static_cast<int>(edges.size()) - 1);
            int y2 = randint(0, static_cast<int>(edges.size()) - 2);
            if (y2 >= y1) ++y2;
            if (y1 < y2) swap(y1, y2);
            for (int y : {y1, y2}) {
                est_sizes -= connection_dist(connections[y]);
                connections.erase(connections.begin() + y);
                edges.erase(edges.begin() + y);
            }
            edges.push_back(x);
            connections.push_back(edge_candidates[x]);
            est_sizes += connection_dist(edge_candidates[x]);
        } else {
            int y = randint(0, static_cast<int>(edges.size()) - 1);
            est_sizes -= connection_dist(connections[y]);
            edges[y] = x;
            connections[y] = edge_candidates[x];
            est_sizes += connection_dist(edge_candidates[x]);
        }
        auto trees = build_trees(connections);
        long long new_score = evalulate(trees);
        if (new_score <= current_score || r < exp((current_score - new_score) / temperature)) {
            current_score = static_cast<double>(new_score);
        } else {
            edges = std::move(prev_edges);
            connections = std::move(prev_connections);
            est_sizes = prev_est_sizes;
        }
        if (new_score < best_score) {
            best_trees = std::move(trees);
            best_score = new_score;
        }
    }
    cout << best_trees.size() << '\n';
    for (int v : best_trees) {
        auto [x, y] = to_2d(v);
        cout << x - 1 << ' ' << y - 1 << '\n';
    }
    return 0;
}