#1195023 (C++23) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: Piiiii
• 提出日時: 2026-10-24 16:02:48
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,941 ms / 2,000 ms
• コード長: 9,099 bytes
• コンパイル時間: 3,024 ms
• コンパイル使用メモリ: 356,408 KB
• 実行使用メモリ: 9,928 KB
• スコア: 126,717,103
• 最終ジャッジ日時: 2026-10-24 16:05:28
• 合計ジャッジ時間: 159,494 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

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

ソースコード

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

// 指定された範囲での機械的な比較結果により、開始温度200、終了温度0.01とする。
// 必要なら -DSTART_TEMP=<値> -DEND_TEMP=<値> で変更できる。
#ifndef START_TEMP
#define START_TEMP 200.0
#endif
#ifndef END_TEMP
#define END_TEMP 0.01
#endif

constexpr double TIME_LIMIT_MS = 1950.0;
constexpr double INITIAL_TEMP = START_TEMP;
constexpr double FINAL_TEMP = END_TEMP;

// 乾燥木かつ未伐採のマスについて、4近傍の連結成分を管理する。
// 伐採位置1個と未伐採位置1個を交換する候補について、
// 影響を受ける成分だけを調べて評価値の差分を計算する。
struct IncrementalComponents {
    int n;
    vector<uint8_t> dry;
    vector<uint8_t> cut;
    vector<array<int, 4>> adj;
    vector<uint8_t> degree;

    vector<int> component;  // -1: 木がない / 伐採済み
    vector<int> sizes;      // 成分番号 -> サイズ
    vector<int> unused_ids;
    long long score = 0;

    // 候補評価の作業領域（確保済みの配列を再利用する）。
    vector<int> seen;
    int stamp = 0;
    vector<int> order;
    vector<pair<int, int>> intervals;
    vector<int> affected_ids;

    IncrementalComponents(int n_, const vector<uint8_t>& dry_,
                          const vector<uint8_t>& initial_cut)
        : n(n_), dry(dry_), cut(initial_cut),
          adj(n_ * n_), degree(n_ * n_, 0),
          component(n_ * n_, -1), seen(n_ * n_, 0) {
        const int total = n * n;
        order.reserve(total);
        intervals.reserve(5);
        affected_ids.reserve(5);
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                int v = r * n + c;
                if (r > 0) adj[v][degree[v]++] = v - n;
                if (r + 1 < n) adj[v][degree[v]++] = v + n;
                if (c > 0) adj[v][degree[v]++] = v - 1;
                if (c + 1 < n) adj[v][degree[v]++] = v + 1;
            }
        }

        // 初回だけ全成分を構築する。
        for (int v = 0; v < total; ++v) {
            if (!dry[v] || cut[v] || component[v] != -1) continue;
            const int id = static_cast<int>(sizes.size());
            int head = 0;
            order.clear();
            order.push_back(v);
            component[v] = id;
            while (head < static_cast<int>(order.size())) {
                const int x = order[head++];
                for (int j = 0; j < degree[x]; ++j) {
                    int y = adj[x][j];
                    if (!dry[y] || cut[y] || component[y] != -1) continue;
                    component[y] = id;
                    order.push_back(y);
                }
            }
            const int s = static_cast<int>(order.size());
            sizes.push_back(s);
            score += 1LL * s * s;
        }
        order.clear();
    }

    // add: 現在伐採されていて、木を戻すマス
    // remove: 現在木があって、新たに伐採するマス
    // 候補はまだ確定せず、現在の component/cut/score は変更しない。
    long long evaluate_swap(int add, int remove) {
        affected_ids.clear();
        intervals.clear();
        order.clear();
        ++stamp;

        auto add_old_component = [&](int id) {
            if (id < 0) return;
            for (int x : affected_ids) if (x == id) return;
            affected_ids.push_back(id);
        };

        // remove を含む旧成分と、add の隣接先の旧成分だけが変わり得る。
        add_old_component(component[remove]);
        for (int j = 0; j < degree[add]; ++j) {
            add_old_component(component[adj[add][j]]);
        }

        long long before = 0;
        for (int id : affected_ids) before += 1LL * sizes[id] * sizes[id];

        // 交換後の盤面を仮想的に参照する。配列 cut は更新しない。
        auto alive_after_swap = [&](int v) {
            return v == add || (v != remove && dry[v] && !cut[v]);
        };

        long long after = 0;
        auto visit_new_component = [&](int root) {
            if (!alive_after_swap(root) || seen[root] == stamp) return;
            const int begin = static_cast<int>(order.size());
            int head = begin;
            seen[root] = stamp;
            order.push_back(root);
            while (head < static_cast<int>(order.size())) {
                int x = order[head++];
                for (int j = 0; j < degree[x]; ++j) {
                    int y = adj[x][j];
                    if (!alive_after_swap(y) || seen[y] == stamp) continue;
                    seen[y] = stamp;
                    order.push_back(y);
                }
            }
            const int end = static_cast<int>(order.size());
            intervals.emplace_back(begin, end);
            long long s = end - begin;
            after += s * s;
        };

        // add を含む新成分と、remove を除いた旧成分の断片を列挙する。
        visit_new_component(add);
        for (int j = 0; j < degree[remove]; ++j) {
            visit_new_component(adj[remove][j]);
        }
        return after - before;
    }

    // evaluate_swap(add, remove) の直後に、同じ交換を確定する。
    // 差分計算で列挙したマスと成分境界を再利用し、全盤面を走査しない。
    void commit_swap(int add, int remove, long long delta) {
        cut[add] = 0;
        cut[remove] = 1;
        component[remove] = -1;

        const int old_count = static_cast<int>(affected_ids.size());
        const int new_count = static_cast<int>(intervals.size());
        for (int i = 0; i < new_count; ++i) {
            int id;
            if (i < old_count) {
                id = affected_ids[i];
            } else if (!unused_ids.empty()) {
                id = unused_ids.back();
                unused_ids.pop_back();
            } else {
                id = static_cast<int>(sizes.size());
                sizes.push_back(0);
            }
            const auto [begin, end] = intervals[i];
            sizes[id] = end - begin;
            for (int j = begin; j < end; ++j) {
                component[order[j]] = id;
            }
        }
        // 再利用されなかった旧成分番号を解放する。
        for (int i = new_count; i < old_count; ++i) {
            const int id = affected_ids[i];
            sizes[id] = 0;
            unused_ids.push_back(id);
        }
        score += delta;
    }
};

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

    int n, K;
    cin >> n >> K;
    if (!cin) return 0;

    vector<uint8_t> dry(n * n, 0);
    vector<int> dry_cells;
    for (int r = 0; r < n; ++r) {
        string row;
        cin >> row;
        for (int c = 0; c < n; ++c) {
            if (row[c] >= '6') {
                int p = r * n + c;
                dry[p] = 1;
                dry_cells.push_back(p);
            }
        }
    }

    mt19937_64 rng(
        static_cast<uint64_t>(chrono::steady_clock::now().time_since_epoch().count())
    );
    shuffle(dry_cells.begin(), dry_cells.end(), rng);

    const int m = min(K, static_cast<int>(dry_cells.size()));
    vector<int> cut_cells(dry_cells.begin(), dry_cells.begin() + m);
    vector<int> uncut_cells(dry_cells.begin() + m, dry_cells.end());
    vector<uint8_t> cut(n * n, 0);
    for (int p : cut_cells) cut[p] = 1;

    vector<int> best_cuts = cut_cells;

    if (m > 0 && !uncut_cells.empty()) {
        IncrementalComponents state(n, dry, cut);
        long long best_score = state.score;
        uniform_real_distribution<double> real01(0.0, 1.0);
        uniform_int_distribution<int> cut_dist(0, m - 1);
        uniform_int_distribution<int> uncut_dist(0, static_cast<int>(uncut_cells.size()) - 1);

        const auto start = chrono::steady_clock::now();
        while (true) {
            double elapsed_ms = chrono::duration<double, milli>(
                chrono::steady_clock::now() - start
            ).count();
            if (elapsed_ms >= TIME_LIMIT_MS) break;

            const double progress = elapsed_ms / TIME_LIMIT_MS;
            const double temp = INITIAL_TEMP + (FINAL_TEMP - INITIAL_TEMP) * progress;

            const int ci = cut_dist(rng);
            const int ui = uncut_dist(rng);
            const int add = cut_cells[ci];
            const int remove = uncut_cells[ui];
            const long long delta = state.evaluate_swap(add, remove);

            bool accept = (delta <= 0);
            if (!accept && temp > 0.0) {
                accept = (real01(rng) < exp(-static_cast<double>(delta) / temp));
            }
            if (accept) {
                state.commit_swap(add, remove, delta);
                swap(cut_cells[ci], uncut_cells[ui]);
                if (state.score < best_score) {
                    best_score = state.score;
                    best_cuts = cut_cells;
                }
            }
        }
    }

    cout << best_cuts.size() << '\n';
    for (int p : best_cuts) cout << (p / n) << ' ' << (p % n) << '\n';
}