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

• 問題: No.5025 Forest Fire
• ユーザー: kaede2020
• 提出日時: 2026-10-24 16:44:14
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 8,947 bytes
• コンパイル時間: 1,997 ms
• コンパイル使用メモリ: 239,448 KB
• 実行使用メモリ: 9,928 KB
• スコア: 64,929,322
• 最終ジャッジ日時: 2026-10-24 16:45:40
• 合計ジャッジ時間: 55,602 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

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

ソースコード

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>

using Clock = std::chrono::steady_clock;

struct Input {
    int N = 0;
    int K = 0;
    std::vector<std::vector<int>> d;
};

struct Output {
    std::vector<std::pair<int, int>> cut_trees;
};

Input read_input(std::istream& in = std::cin) {
    Input input;
    in >> input.N >> input.K;
    input.d.assign(input.N, std::vector<int>(input.N));
    for (int i = 0; i < input.N; ++i) {
        for (int j = 0; j < input.N; ++j) {
            char digit;
            in >> digit;
            input.d[i][j] = digit - '0';
        }
    }
    return input;
}

void print_output(const Output& output, std::ostream& out = std::cout) {
    out << output.cut_trees.size() << '\n';
    for (const auto& [i, j] : output.cut_trees) {
        out << i << ' ' << j << '\n';
    }
}

long long calc_score(double E0, double E) {
    return std::llround(1'000'000.0 * (1.0 + std::log2(E0 / E)));
}

bool inside(int n, int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < n;
}

struct CutLine {
    std::vector<int> cells;
};

// 逆向きにたどった線は同じ候補なので、各傾きについて一度だけ列挙する。
// 元の水または盤外で区切られる線を最後まで取り、途中に乾燥度1〜7が
// あれば候補にしない。水のマス自体は伐採しない。
std::vector<CutLine> make_lines(
    const Input& input, const std::vector<std::pair<int, int>>& directions) {
    std::vector<CutLine> lines;
    for (const auto& [di, dj] : directions) {
        for (int i = 0; i < input.N; ++i) {
            for (int j = 0; j < input.N; ++j) {
                if (input.d[i][j] == 0) continue;
                const int pi = i - di;
                const int pj = j - dj;
                if (inside(input.N, pi, pj) && input.d[pi][pj] != 0) {
                    continue;
                }

                CutLine line;
                bool allowed = true;
                for (int y = i, x = j;
                     inside(input.N, y, x) && input.d[y][x] != 0;
                     y += di, x += dj) {
                    if (input.d[y][x] != 8 && input.d[y][x] != 9) {
                        allowed = false;
                    }
                    line.cells.push_back(y * input.N + x);
                }
                if (allowed) lines.push_back(std::move(line));
            }
        }
    }
    return lines;
}

class ComponentCounter {
public:
    explicit ComponentCounter(int n)
        : neighbors_(n * n), visited_(n * n, 0), queue_(n * n) {
        constexpr int di[4] = {-1, 1, 0, 0};
        constexpr int dj[4] = {0, 0, -1, 1};
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < 4; ++k) {
                    const int y = i + di[k];
                    const int x = j + dj[k];
                    neighbors_[i * n + j][k] =
                        inside(n, y, x) ? y * n + x : -1;
                }
            }
        }
    }

    // 乾燥確率は無視し、残る全ての木を上下左右の連結で数える。
    int largest(const std::vector<unsigned char>& alive) {
        ++stamp_;
        int largest_size = 0;
        for (int cell = 0; cell < static_cast<int>(alive.size()); ++cell) {
            if (!alive[cell] || visited_[cell] == stamp_) continue;
            int head = 0;
            int tail = 0;
            queue_[tail++] = cell;
            visited_[cell] = stamp_;
            while (head < tail) {
                const int current = queue_[head++];
                for (int next : neighbors_[current]) {
                    if (next < 0 || !alive[next] || visited_[next] == stamp_) {
                        continue;
                    }
                    visited_[next] = stamp_;
                    queue_[tail++] = next;
                }
            }
            largest_size = std::max(largest_size, tail);
        }
        return largest_size;
    }

private:
    std::vector<std::array<int, 4>> neighbors_;
    std::vector<int> visited_;
    std::vector<int> queue_;
    int stamp_ = 0;
};

struct SearchStatistics {
    int evaluated_candidates = 0;
    int diagonal_lines = 0;
    int orthogonal_lines = 0;
    int initial_largest = 0;
    int final_largest = 0;
    bool used_center_cross = false;
    double elapsed_seconds = 0.0;
};

struct LineSelection {
    std::vector<int> new_cuts;
    int largest_size = 0;
};

std::optional<LineSelection> select_line(
    const std::vector<CutLine>& lines, int remaining,
    std::vector<unsigned char>& alive, ComponentCounter& counter,
    Clock::time_point deadline, SearchStatistics& statistics) {
    std::optional<LineSelection> best;
    for (const auto& line : lines) {
        if (Clock::now() >= deadline) break;

        std::vector<int> new_cuts;
        for (int cell : line.cells) {
            if (alive[cell]) new_cuts.push_back(cell);
        }
        if (new_cuts.empty() || static_cast<int>(new_cuts.size()) > remaining) {
            continue;
        }

        for (int cell : new_cuts) alive[cell] = 0;
        const int largest_size = counter.largest(alive);
        for (int cell : new_cuts) alive[cell] = 1;
        ++statistics.evaluated_candidates;

        // 同値なら列挙順を維持し、追加の評価基準は使わない。
        if (!best || largest_size < best->largest_size) {
            best = LineSelection{std::move(new_cuts), largest_size};
        }
    }
    return best;
}

Output center_cross(const Input& input) {
    Output output;
    const int center = input.N / 2;
    const auto add = [&](int i, int j) {
        if (inside(input.N, i, j) && input.d[i][j] != 0 &&
            static_cast<int>(output.cut_trees.size()) < input.K) {
            output.cut_trees.emplace_back(i, j);
        }
    };

    // 代替の十字では乾燥度8・9の制限と連続性を無視する。
    add(center, center);
    for (int distance = 1; distance < input.N; ++distance) {
        add(center - distance, center);
        add(center + distance, center);
        add(center, center - distance);
        add(center, center + distance);
    }
    return output;
}

Output solve(const Input& input,
             Clock::time_point process_start = Clock::now(),
             SearchStatistics* result_statistics = nullptr) {
    const auto deadline = process_start + std::chrono::milliseconds(1950);
    SearchStatistics statistics;
    ComponentCounter counter(input.N);
    std::vector<unsigned char> alive(input.N * input.N, 0);
    for (int i = 0; i < input.N; ++i) {
        for (int j = 0; j < input.N; ++j) {
            alive[i * input.N + j] = input.d[i][j] != 0;
        }
    }
    statistics.initial_largest = counter.largest(alive);
    statistics.final_largest = statistics.initial_largest;

    // 45度・135度の2つの傾き。逆方向を含めて斜め4方向に対応する。
    const auto diagonal_lines = make_lines(input, {{1, 1}, {1, -1}});
    const auto orthogonal_lines = make_lines(input, {{1, 0}, {0, 1}});
    Output output;
    while (static_cast<int>(output.cut_trees.size()) < input.K &&
           Clock::now() < deadline) {
        const int remaining = input.K - static_cast<int>(output.cut_trees.size());
        auto selection = select_line(diagonal_lines, remaining, alive, counter,
                                     deadline, statistics);
        bool diagonal = true;
        if (!selection && Clock::now() < deadline) {
            diagonal = false;
            selection = select_line(orthogonal_lines, remaining, alive, counter,
                                    deadline, statistics);
        }
        if (!selection) break;

        for (int cell : selection->new_cuts) {
            alive[cell] = 0;
            output.cut_trees.emplace_back(cell / input.N, cell % input.N);
        }
        statistics.final_largest = selection->largest_size;
        if (diagonal) {
            ++statistics.diagonal_lines;
        } else {
            ++statistics.orthogonal_lines;
        }
    }

    if (output.cut_trees.empty()) {
        output = center_cross(input);
        statistics.used_center_cross = true;
        for (const auto& [i, j] : output.cut_trees) {
            alive[i * input.N + j] = 0;
        }
        statistics.final_largest = counter.largest(alive);
    }
    statistics.elapsed_seconds =
        std::chrono::duration<double>(Clock::now() - process_start).count();
    if (result_statistics) *result_statistics = statistics;
    return output;
}

int main() {
    const auto process_start = Clock::now();
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    const Input input = read_input();
    SearchStatistics statistics;
    const Output output = solve(input, process_start, &statistics);
    print_output(output);
    return 0;
}