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

• 問題: No.5025 Forest Fire
• ユーザー: Shun_PI
• 提出日時: 2026-10-24 15:22:58
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 72 ms / 2,000 ms
• コード長: 8,677 bytes
• コンパイル時間: 6,415 ms
• コンパイル使用メモリ: 396,996 KB
• 実行使用メモリ: 9,928 KB
• スコア: 95,238,185
• 最終ジャッジ日時: 2026-10-24 15:24:04
• 合計ジャッジ時間: 66,544 ms
• ジャッジサーバーID （参考情報）: judge1_0 / <nil>

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

ソースコード

#include <string>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using P = pair<int, int>;
using PL = pair<lint, lint>;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
constexpr int MOD = 1000000007;
vector<lint> RH_B = {1532834020, 1388622299};
vector<lint> RH_M = {2147482409, 2147478017};
constexpr int INF = 2147483647;
void yes(bool expr) {cout << (expr ? "Yes" : "No") << "\n";}
template<class T>void chmax(T &a, const T &b) { if (a<b) a=b; }
template<class T>void chmin(T &a, const T &b) { if (b<a) a=b; }

struct GridGraph {
    int n;
    int cells;
    vector<array<int, 4>> neighbors;

    explicit GridGraph(int side) : n(side), cells(n * n), neighbors(cells) {
        constexpr int dr[4] = {-1, 1, 0, 0};
        constexpr int dc[4] = {0, 0, -1, 1};
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                auto &adj = neighbors[r * n + c];
                adj.fill(-1);
                for (int direction = 0; direction < 4; ++direction) {
                    int nr = r + dr[direction];
                    int nc = c + dc[direction];
                    if (0 <= nr && nr < n && 0 <= nc && nc < n) {
                        adj[direction] = nr * n + nc;
                    }
                }
            }
        }
    }
};

struct DrySample {
    vector<unsigned char> dry;
    vector<long long> decrease;
    vector<unsigned char> articulation;

    explicit DrySample(vector<unsigned char> state)
        : dry(move(state)), decrease(dry.size()), articulation(dry.size()),
          order(dry.size()), low(dry.size()), subtree_size(dry.size()),
          separated_size(dry.size()), separated_parts(dry.size()),
          separated_squares(dry.size()) {
        component.reserve(dry.size());
    }

    void recompute(const GridGraph &graph) {
        fill(order.begin(), order.end(), -1);
        fill(decrease.begin(), decrease.end(), 0);
        fill(articulation.begin(), articulation.end(), 0);
        timer = 0;
        for (int root = 0; root < graph.cells; ++root) {
            if (!dry[root] || order[root] != -1) continue;
            component.clear();
            dfs(root, -1, graph);
            const long long size = subtree_size[root];
            for (int v : component) {
                // 削除で分離する子部分木と、残る親側の成分のサイズを使う。
                const long long rest = size - 1 - separated_size[v];
                articulation[v] = separated_parts[v] + (rest > 0) >= 2;
                // 関節点でない木の評価値は指定どおり 0 にする。
                if (articulation[v]) {
                    decrease[v] = size * size - separated_squares[v] - rest * rest;
                }
            }
        }
    }

private:
    vector<int> order, low, subtree_size, separated_size, separated_parts;
    vector<long long> separated_squares;
    vector<int> component;
    int timer = 0;

    void dfs(int v, int parent, const GridGraph &graph) {
        order[v] = low[v] = timer++;
        subtree_size[v] = 1;
        separated_size[v] = separated_parts[v] = 0;
        separated_squares[v] = 0;
        component.push_back(v);
        for (int next : graph.neighbors[v]) {
            if (next == -1 || !dry[next] || next == parent) continue;
            if (order[next] == -1) {
                dfs(next, v, graph);
                subtree_size[v] += subtree_size[next];
                low[v] = min(low[v], low[next]);
                if (low[next] >= order[v]) {
                    const long long size = subtree_size[next];
                    separated_size[v] += static_cast<int>(size);
                    separated_squares[v] += size * size;
                    ++separated_parts[v];
                }
            } else {
                low[v] = min(low[v], order[next]);
            }
        }
    }
};

// 提出時のサンプリング回数。実行時は --samples X でも変更できる。
constexpr int DEFAULT_SAMPLE_COUNT = 10;
constexpr int SCORE_SAMPLE_COUNT = 100;

long long component_square_sum(const GridGraph &graph,
                               const vector<unsigned char> &dry) {
    vector<unsigned char> visited(graph.cells, false);
    vector<int> component;
    component.reserve(graph.cells);
    long long total = 0;
    for (int root = 0; root < graph.cells; ++root) {
        if (!dry[root] || visited[root]) continue;
        component.clear();
        component.push_back(root);
        visited[root] = true;
        for (size_t head = 0; head < component.size(); ++head) {
            for (int next : graph.neighbors[component[head]]) {
                if (next == -1 || !dry[next] || visited[next]) continue;
                visited[next] = true;
                component.push_back(next);
            }
        }
        const long long size = static_cast<long long>(component.size());
        total += size * size;
    }
    return total;
}

int main(int argc, char **argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int sample_count = DEFAULT_SAMPLE_COUNT;
    if (argc != 1) {
        if (argc != 3 || string(argv[1]) != "--samples") {
            cerr << "Usage: " << argv[0] << " [--samples X]\n";
            return 1;
        }
        const char *begin = argv[2];
        const char *end = begin + strlen(begin);
        auto parsed = from_chars(begin, end, sample_count);
        if (parsed.ec != errc{} || parsed.ptr != end || sample_count <= 0) {
            cerr << "X must be a positive integer.\n";
            return 1;
        }
    }

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<string> board(n);
    for (auto &row : board) cin >> row;

    GridGraph graph(n);
    vector<unsigned char> available(graph.cells);
    for (int v = 0; v < graph.cells; ++v) {
        available[v] = board[v / n][v % n] != '0';
    }

    // 最初に一度だけ生成し、全 K 回で同じサンプルを共用する。
    mt19937 rng(0);
    uniform_int_distribution<int> random_digit(0, 9);
    vector<DrySample> samples;
    samples.reserve(sample_count);
    for (int s = 0; s < sample_count; ++s) {
        vector<unsigned char> dry(graph.cells);
        for (int v = 0; v < graph.cells; ++v) {
            int dryness = board[v / n][v % n] - '0';
            dry[v] = random_digit(rng) < dryness;
        }
        samples.emplace_back(move(dry));
    }

    vector<int> answer;
    for (int step = 0; step < k; ++step) {
        vector<long long> total_decrease(graph.cells, 0);
        for (auto &sample : samples) {
            sample.recompute(graph);
            for (int v = 0; v < graph.cells; ++v) {
                total_decrease[v] += sample.decrease[v];
            }
        }

        // 共通の X で割る前の合計で、期待値の大小を比較できる。
        // 行・列順に走査し、同点では先に見つかったマスを選ぶ。
        int best = -1;
        for (int v = 0; v < graph.cells; ++v) {
            if (!available[v]) continue;
            if (best == -1 || total_decrease[v] > total_decrease[best]) best = v;
        }
        if (best == -1) break;
        answer.push_back(best);
        available[best] = false;
        for (auto &sample : samples) sample.dry[best] = false;
    }

    cout << answer.size() << '\n';
    for (int v : answer) cout << v / n << ' ' << v % n << '\n';

    // 伐採の選択に使ったサンプルとは別に、100 個を新しく生成する。
    // 各サンプルを伐採前・伐採後で共用して E0 と E を推定する。
    long long before_sum = 0, after_sum = 0;
    for (int s = 0; s < SCORE_SAMPLE_COUNT; ++s) {
        vector<unsigned char> dry(graph.cells);
        for (int v = 0; v < graph.cells; ++v) {
            int dryness = board[v / n][v % n] - '0';
            dry[v] = random_digit(rng) < dryness;
        }
        before_sum += component_square_sum(graph, dry);
        for (int v : answer) dry[v] = false;
        after_sum += component_square_sum(graph, dry);
    }
    const long double denominator = 1.0L * SCORE_SAMPLE_COUNT * graph.cells;
    const long double e0 = before_sum / denominator;
    const long double e = after_sum / denominator;
    const long double score = round(1.0e6L * (1.0L + log2(e0 / e)));
    cerr << fixed << setprecision(0) << score << '\n';
    return 0;
}