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

• 問題: No.5025 Forest Fire
• ユーザー: 秋ナス🍆
• 提出日時: 2026-10-24 17:17:03
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,942 ms / 2,000 ms
• コード長: 11,731 bytes
• コンパイル時間: 3,238 ms
• コンパイル使用メモリ: 256,768 KB
• 実行使用メモリ: 9,924 KB
• スコア: 157,943,014
• 最終ジャッジ日時: 2026-10-24 17:21:39
• 合計ジャッジ時間: 159,300 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

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

ソースコード

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <random>
#include <string>
#include <vector>

using namespace std;

const int N = 50;
const int K_MAX = 100;

const int THRESHOLD_D = 5;

int D[N][N];

struct XorShift {
    unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int next() {
        unsigned int t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
    double next_double() { return (next() & 0xFFFFFFF) / (double)0x10000000; }
    int next_int(int n) { return next() % n; }
} rng;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    auto start_time = chrono::steady_clock::now();
    const double TIME_LIMIT = 1.95;

    int n_in, k_in;
    if (!(cin >> n_in >> k_in)) return 0;

    for (int r = 0; r < N; ++r) {
        string s;
        cin >> s;
        for (int c = 0; c < N; ++c) {
            D[r][c] = s[c] - '0';
        }
    }

    int cr = 24, cc = 24;
    if (D[cr][cc] == 0) {
        int best_dist = 1e9;
        int best_r = -1, best_c = -1;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (D[r][c] >= 1) {
                    int dist = abs(r - 24) + abs(c - 24);
                    if (dist < best_dist) {
                        best_dist = dist;
                        best_r = r;
                        best_c = c;
                    }
                }
            }
        }
        cr = best_r;
        cc = best_c;
    }

    int len_up = cr;
    int len_right = N - 1 - cc;
    int len_down = N - 1 - cr;
    int len_left = cc;

    vector<int> up_diff(len_up, 0);
    vector<int> right_diff(len_right, 0);
    vector<int> down_diff(len_down, 0);
    vector<int> left_diff(len_left, 0);

    auto get_offsets = [](const vector<int>& diff) {
        vector<int> off(diff.size(), 0);
        int cur = 0;
        for (size_t i = 0; i < diff.size(); ++i) {
            cur += diff[i];
            off[i] = cur;
        }
        return off;
    };

    static int grid_type[N][N];

    auto evaluate = [&](const vector<int>& u_off, const vector<int>& r_off, const vector<int>& d_off, const vector<int>& l_off) -> double {
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                grid_type[r][c] = -2;
            }
        }

        double wall_bonus = 0.0;

        auto mark_arm = [&](int r, int c) {
            grid_type[r][c] = -1;

            if (D[r][c] == 0)
                wall_bonus += 15.0;
            else if (D[r][c] < THRESHOLD_D)
                wall_bonus += (THRESHOLD_D - D[r][c]) * 2.0;
        };

        mark_arm(cr, cc);
        for (int i = 0; i < len_up; ++i)
            mark_arm(cr - 1 - i, cc + u_off[i]);
        for (int i = 0; i < len_right; ++i)
            mark_arm(cr + r_off[i], cc + 1 + i);
        for (int i = 0; i < len_down; ++i)
            mark_arm(cr + 1 + i, cc - d_off[i]);
        for (int i = 0; i < len_left; ++i)
            mark_arm(cr - l_off[i], cc - 1 - i);

        double quad_weight[4] = {0.0, 0.0, 0.0, 0.0};

        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (grid_type[r][c] == -1) continue;

                int quad = -1;
                if (r < cr) {
                    int up_c = cc + u_off[cr - 1 - r];
                    if (c >= up_c) {
                        quad = 0;
                    } else {
                        int left_r = (c < cc) ? (cr - l_off[cc - 1 - c]) : cr;
                        quad = (r < left_r) ? 3 : 2;
                    }
                } else {
                    int down_c = cc - d_off[r - 1 - cr];
                    if (c <= down_c) {
                        quad = 2;
                    } else {
                        int right_r = (c > cc) ? (cr + r_off[c - 1 - cc]) : cr;
                        quad = (r > right_r) ? 1 : 0;
                    }
                }

                if (D[r][c] >= THRESHOLD_D) {
                    quad_weight[quad] += D[r][c];
                }
            }
        }

        double fire_hazard = 0.0;
        for (int k = 0; k < 4; ++k) {
            fire_hazard += quad_weight[k] * quad_weight[k];
        }

        return -(fire_hazard * 0.001) + wall_bonus;
    };

    vector<int> cur_u_off = get_offsets(up_diff);
    vector<int> cur_r_off = get_offsets(right_diff);
    vector<int> cur_d_off = get_offsets(down_diff);
    vector<int> cur_l_off = get_offsets(left_diff);

    double cur_score = evaluate(cur_u_off, cur_r_off, cur_d_off, cur_l_off);
    double best_score = cur_score;

    vector<int> best_up_diff = up_diff;
    vector<int> best_right_diff = right_diff;
    vector<int> best_down_diff = down_diff;
    vector<int> best_left_diff = left_diff;

    const double T_START = 10.0;
    const double T_END = 0.01;

    long long iterations = 0;

    while (true) {
        if ((iterations & 255) == 0) {
            auto now = chrono::steady_clock::now();
            double elapsed = chrono::duration<double>(now - start_time).count();
            if (elapsed >= TIME_LIMIT) break;
        }
        iterations++;

        double progress =
            (iterations & 1023) == 0 ? chrono::duration<double>(chrono::steady_clock::now() - start_time).count() / TIME_LIMIT : 0.0;
        if (progress > 1.0) progress = 1.0;
        double temp = T_START * pow(T_END / T_START, progress);

        int arm = rng.next_int(4);
        int pos = -1;
        bool valid = false;

        if (arm == 0 && len_up > 0) {
            pos = rng.next_int(len_up);
            int orig = up_diff[pos];
            up_diff[pos] = 1 - orig;

            auto next_u_off = get_offsets(up_diff);
            valid = true;
            for (int i = 0; i < len_up; ++i) {
                if (cc + next_u_off[i] >= N) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                double next_score = evaluate(next_u_off, cur_r_off, cur_d_off, cur_l_off);
                double delta = next_score - cur_score;
                if (delta >= 0 || exp(delta / temp) > rng.next_double()) {
                    cur_score = next_score;
                    cur_u_off = next_u_off;
                    if (cur_score > best_score) {
                        best_score = cur_score;
                        best_up_diff = up_diff;
                        best_right_diff = right_diff;
                        best_down_diff = down_diff;
                        best_left_diff = left_diff;
                    }
                } else {
                    up_diff[pos] = orig;
                }
            } else {
                up_diff[pos] = orig;
            }
        } else if (arm == 1 && len_right > 0) {
            pos = rng.next_int(len_right);
            int orig = right_diff[pos];
            right_diff[pos] = 1 - orig;

            auto next_r_off = get_offsets(right_diff);
            valid = true;
            for (int i = 0; i < len_right; ++i) {
                if (cr + next_r_off[i] >= N) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                double next_score = evaluate(cur_u_off, next_r_off, cur_d_off, cur_l_off);
                double delta = next_score - cur_score;
                if (delta >= 0 || exp(delta / temp) > rng.next_double()) {
                    cur_score = next_score;
                    cur_r_off = next_r_off;
                    if (cur_score > best_score) {
                        best_score = cur_score;
                        best_up_diff = up_diff;
                        best_right_diff = right_diff;
                        best_down_diff = down_diff;
                        best_left_diff = left_diff;
                    }
                } else {
                    right_diff[pos] = orig;
                }
            } else {
                right_diff[pos] = orig;
            }
        } else if (arm == 2 && len_down > 0) {
            pos = rng.next_int(len_down);
            int orig = down_diff[pos];
            down_diff[pos] = 1 - orig;

            auto next_d_off = get_offsets(down_diff);
            valid = true;
            for (int i = 0; i < len_down; ++i) {
                if (cc - next_d_off[i] < 0) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                double next_score = evaluate(cur_u_off, cur_r_off, next_d_off, cur_l_off);
                double delta = next_score - cur_score;
                if (delta >= 0 || exp(delta / temp) > rng.next_double()) {
                    cur_score = next_score;
                    cur_d_off = next_d_off;
                    if (cur_score > best_score) {
                        best_score = cur_score;
                        best_up_diff = up_diff;
                        best_right_diff = right_diff;
                        best_down_diff = down_diff;
                        best_left_diff = left_diff;
                    }
                } else {
                    down_diff[pos] = orig;
                }
            } else {
                down_diff[pos] = orig;
            }
        } else if (arm == 3 && len_left > 0) {
            pos = rng.next_int(len_left);
            int orig = left_diff[pos];
            left_diff[pos] = 1 - orig;

            auto next_l_off = get_offsets(left_diff);
            valid = true;
            for (int i = 0; i < len_left; ++i) {
                if (cr - next_l_off[i] < 0) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                double next_score = evaluate(cur_u_off, cur_r_off, cur_d_off, next_l_off);
                double delta = next_score - cur_score;
                if (delta >= 0 || exp(delta / temp) > rng.next_double()) {
                    cur_score = next_score;
                    cur_l_off = next_l_off;
                    if (cur_score > best_score) {
                        best_score = cur_score;
                        best_up_diff = up_diff;
                        best_right_diff = right_diff;
                        best_down_diff = down_diff;
                        best_left_diff = left_diff;
                    }
                } else {
                    left_diff[pos] = orig;
                }
            } else {
                left_diff[pos] = orig;
            }
        }
    }

    auto best_u_off = get_offsets(best_up_diff);
    auto best_r_off = get_offsets(best_right_diff);
    auto best_d_off = get_offsets(best_down_diff);
    auto best_l_off = get_offsets(best_left_diff);

    vector<pair<int, int>> cuts;
    vector<vector<bool>> visited(N, vector<bool>(N, false));

    auto add_cut = [&](int r, int c) {
        if (r >= 0 && r < N && c >= 0 && c < N) {
            if (!visited[r][c] && D[r][c] >= 1) {
                visited[r][c] = true;
                cuts.push_back({r, c});
            }
        }
    };

    add_cut(cr, cc);
    for (int i = 0; i < len_up; ++i)
        add_cut(cr - 1 - i, cc + best_u_off[i]);
    for (int i = 0; i < len_right; ++i)
        add_cut(cr + best_r_off[i], cc + 1 + i);
    for (int i = 0; i < len_down; ++i)
        add_cut(cr + 1 + i, cc - best_d_off[i]);
    for (int i = 0; i < len_left; ++i)
        add_cut(cr - best_l_off[i], cc - 1 - i);

    int M = min((int)cuts.size(), K_MAX);
    cout << M << "\n";
    for (int i = 0; i < M; ++i) {
        cout << cuts[i].first << " " << cuts[i].second << "\n";
    }

    return 0;
}