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

• 問題: No.5025 Forest Fire
• ユーザー: kaede2020
• 提出日時: 2026-10-24 17:44:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,941 ms / 2,000 ms
• コード長: 17,193 bytes
• コンパイル時間: 3,167 ms
• コンパイル使用メモリ: 286,160 KB
• 実行使用メモリ: 9,928 KB
• スコア: 144,221,967
• 最終ジャッジ日時: 2026-10-24 17:49:28
• 合計ジャッジ時間: 159,077 ms
• ジャッジサーバーID （参考情報）: judge1_0 / <nil>

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

ソースコード

#include <algorithm>
#include <array>
#include <chrono>
#include <cmath>
#include <iostream>
#include <map>
#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 (auto& row : input.d) {
        for (int& value : row) {
            char digit;
            in >> digit;
            value = 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)));
}

struct Area {
    int size = 0;
    int dryness_sum = 0;

    double mean() const { return static_cast<double>(dryness_sum) / size; }
};

struct AreaMap {
    std::vector<int> labels;
    std::vector<Area> areas;
};

class AreaCounter {
public:
    explicit AreaCounter(const Input& input)
        : n_(input.N), dryness_(n_ * n_), neighbors_(n_ * n_),
          visited_(n_ * n_, 0), queue_(n_ * n_) {
        constexpr int di[] = {-1, 1, 0, 0};
        constexpr int dj[] = {0, 0, -1, 1};
        for (int i = 0; i < n_; ++i) {
            for (int j = 0; j < n_; ++j) {
                const int cell = i * n_ + j;
                dryness_[cell] = input.d[i][j];
                for (int k = 0; k < 4; ++k) {
                    const int y = i + di[k], x = j + dj[k];
                    neighbors_[cell][k] =
                        0 <= y && y < n_ && 0 <= x && x < n_ ? y * n_ + x : -1;
                }
            }
        }
    }

    // 乾燥確率を無視し、残る木を上下左右で連結する。
    AreaMap analyze(const std::vector<unsigned char>& cut) const {
        AreaMap result;
        result.labels.assign(n_ * n_, -1);
        for (int cell = 0; cell < n_ * n_; ++cell) {
            if (!dryness_[cell] || cut[cell] || result.labels[cell] >= 0) continue;
            const int label = static_cast<int>(result.areas.size());
            Area area;
            int head = 0, tail = 0;
            queue_[tail++] = cell;
            result.labels[cell] = label;
            while (head < tail) {
                const int current = queue_[head++];
                ++area.size;
                area.dryness_sum += dryness_[current];
                for (int next : neighbors_[current]) {
                    if (next < 0 || !dryness_[next] || cut[next] ||
                        result.labels[next] >= 0) continue;
                    result.labels[next] = label;
                    queue_[tail++] = next;
                }
            }
            result.areas.push_back(area);
        }
        return result;
    }

    // 境界を戻してできた同じエリアが、3エリアに分かれるかを調べる。
    std::optional<std::array<Area, 3>> split_three(
        const std::vector<unsigned char>& target,
        const std::vector<unsigned char>& cut) {
        ++stamp_;
        std::array<Area, 3> result{};
        int count = 0;
        for (int cell = 0; cell < n_ * n_; ++cell) {
            if (!target[cell] || cut[cell] || visited_[cell] == stamp_) continue;
            if (count == 3) return std::nullopt;
            Area& area = result[count++];
            int head = 0, tail = 0;
            queue_[tail++] = cell;
            visited_[cell] = stamp_;
            while (head < tail) {
                const int current = queue_[head++];
                ++area.size;
                area.dryness_sum += dryness_[current];
                for (int next : neighbors_[current]) {
                    if (next < 0 || !target[next] || cut[next] ||
                        visited_[next] == stamp_) continue;
                    visited_[next] = stamp_;
                    queue_[tail++] = next;
                }
            }
        }
        if (count != 3) return std::nullopt;
        return result;
    }

    const std::array<int, 4>& neighbors(int cell) const { return neighbors_[cell]; }

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

double mean_difference(const std::array<Area, 3>& areas) {
    const double a = areas[0].mean(), b = areas[1].mean(), c = areas[2].mean();
    return std::abs(a - b) + std::abs(b - c) + std::abs(c - a);
}

struct Boundary {
    int first = -1;
    int second = -1;
    std::vector<int> cells;
};

// 同じ2エリアに隣接する伐採木を、その2エリア間の境界として集める。
std::vector<Boundary> find_boundaries(const std::vector<unsigned char>& cut,
                                     const AreaMap& map, const AreaCounter& counter) {
    std::map<std::pair<int, int>, std::vector<int>> groups;
    for (int cell = 0; cell < static_cast<int>(cut.size()); ++cell) {
        if (!cut[cell]) continue;
        std::vector<int> adjacent;
        for (int next : counter.neighbors(cell)) {
            if (next >= 0 && map.labels[next] >= 0) adjacent.push_back(map.labels[next]);
        }
        std::sort(adjacent.begin(), adjacent.end());
        adjacent.erase(std::unique(adjacent.begin(), adjacent.end()), adjacent.end());
        for (int a = 0; a < static_cast<int>(adjacent.size()); ++a) {
            for (int b = a + 1; b < static_cast<int>(adjacent.size()); ++b) {
                groups[{adjacent[a], adjacent[b]}].push_back(cell);
            }
        }
    }
    std::vector<Boundary> result;
    for (auto& [pair, cells] : groups) {
        result.push_back({pair.first, pair.second, std::move(cells)});
    }
    // 同じ長さでは元の列挙順を保つ。
    std::stable_sort(result.begin(), result.end(), [](const Boundary& a, const Boundary& b) {
        return a.cells.size() < b.cells.size();
    });
    return result;
}

struct EdgeLine {
    int length = 0;  // 水を含む線上のマス数。既存の伐採木である終点は除く。
    int start = -1;
    int end = -1;
    std::vector<int> cells;  // 実際に新しく伐採する木だけ。
};

constexpr int kPairLength = 25;

// 盤端から既存の伐採木まで、45度または135度の同じ傾きでたどる。
// 水は伐採せず通過し、別の木のエリアには入らない。
std::vector<EdgeLine> make_edge_lines(
    const Input& input, const std::vector<unsigned char>& cut,
    const std::vector<unsigned char>& target, int slope) {
    std::vector<EdgeLine> lines;
    for (int i = 0; i < input.N; ++i) {
        for (int j = 0; j < input.N; ++j) {
            if (i != 0 && i != input.N - 1 && j != 0 && j != input.N - 1) continue;
            for (int sign : {1, -1}) {
                const int di = sign, dj = sign * slope;
                EdgeLine line;
                line.start = i * input.N + j;
                for (int y = i, x = j; 0 <= y && y < input.N && 0 <= x && x < input.N;
                     y += di, x += dj) {
                    const int cell = y * input.N + x;
                    if (cut[cell]) {
                        if (!line.cells.empty() && line.length < kPairLength) {
                            line.end = cell;
                            lines.push_back(std::move(line));
                        }
                        break;
                    }
                    if (input.d[y][x] && !target[cell]) break;
                    ++line.length;
                    if (line.length >= kPairLength) break;
                    if (input.d[y][x]) line.cells.push_back(cell);
                }
            }
        }
    }
    std::stable_sort(lines.begin(), lines.end(), [](const EdgeLine& a, const EdgeLine& b) {
        return a.length < b.length;
    });
    return lines;
}

struct Replacement {
    EdgeLine first;
    EdgeLine second;
    std::array<Area, 3> areas{};
    double value = 0.0;
};

struct MoveRecord {
    std::vector<int> removed;
    Replacement replacement;
    int skipped_shorter_boundaries = 0;
};

struct SearchStatistics {
    long long passes = 0;
    long long boundaries = 0;
    long long candidate_lines = 0;
    long long evaluated_pairs = 0;
    long long valid_pairs = 0;
    int initial_components = 0;
    int final_components = 0;
    double elapsed_seconds = 0.0;
    std::vector<MoveRecord> moves;
};

std::optional<Replacement> select_replacement(
    const Input& input, const std::vector<unsigned char>& target,
    std::vector<unsigned char>& cut, int remaining, AreaCounter& counter,
    Clock::time_point deadline, SearchStatistics& statistics) {
    std::optional<Replacement> best;
    const auto evaluate = [&](const EdgeLine& a, const EdgeLine& b) {
        if (static_cast<int>(a.cells.size() + b.cells.size()) > remaining) return;
        for (int cell : a.cells) cut[cell] = 1;
        bool overlap = false;
        for (int cell : b.cells) if (cut[cell]) overlap = true;
        if (overlap) {
            for (int cell : a.cells) cut[cell] = 0;
            return;
        }
        for (int cell : b.cells) cut[cell] = 1;
        const auto areas = counter.split_three(target, cut);
        for (int cell : a.cells) cut[cell] = 0;
        for (int cell : b.cells) cut[cell] = 0;
        ++statistics.evaluated_pairs;
        if (!areas) return;
        ++statistics.valid_pairs;
        const double value = mean_difference(*areas);
        if (!best || value < best->value) best = Replacement{a, b, *areas, value};
    };

    for (int slope : {1, -1}) {
        if (Clock::now() >= deadline) break;
        const auto lines = make_edge_lines(input, cut, target, slope);
        statistics.candidate_lines += static_cast<long long>(lines.size());
        // 長さ順の両端から動かし、2本の長さの合計25を満たす組を全て試す。
        int left = 0, right = static_cast<int>(lines.size()) - 1;
        while (left < right && Clock::now() < deadline) {
            const int sum = lines[left].length + lines[right].length;
            if (sum < kPairLength) { ++left; continue; }
            if (sum > kPairLength) { --right; continue; }
            int left_end = left + 1;
            while (left_end <= right && lines[left_end].length == lines[left].length) ++left_end;
            int right_begin = right;
            while (right_begin > left && lines[right_begin - 1].length == lines[right].length) --right_begin;
            for (int a = left; a < left_end && Clock::now() < deadline; ++a) {
                for (int b = right_begin; b <= right && Clock::now() < deadline; ++b) {
                    if (a < b) evaluate(lines[a], lines[b]);
                }
            }
            left = left_end;
            right = right_begin - 1;
        }
    }
    return best;
}

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;
    AreaCounter counter(input);
    std::vector<unsigned char> cut(input.N * input.N, 0);
    int cut_count = 0;
    for (int i = 0; i < input.N; ++i) {
        for (int j = 0; j < input.N; ++j) {
            if ((i == j || i + j == input.N - 1) && input.d[i][j] && cut_count < input.K) {
                cut[i * input.N + j] = 1;
                ++cut_count;
            }
        }
    }
    statistics.initial_components = static_cast<int>(counter.analyze(cut).areas.size());

    while (Clock::now() < deadline) {
        ++statistics.passes;
        const AreaMap before = counter.analyze(cut);
        const auto boundaries = find_boundaries(cut, before, counter);
        int skipped = 0;
        for (const Boundary& boundary : boundaries) {
            if (Clock::now() >= deadline) break;
            ++statistics.boundaries;
            for (int cell : boundary.cells) cut[cell] = 0;
            const AreaMap merged = counter.analyze(cut);
            const int label = merged.labels[boundary.cells.front()];
            bool same_area = merged.areas.size() + 1 == before.areas.size();
            for (int cell : boundary.cells) same_area = same_area && merged.labels[cell] == label;
            const int expected_size = before.areas[boundary.first].size +
                before.areas[boundary.second].size + static_cast<int>(boundary.cells.size());
            same_area = same_area && label >= 0 && merged.areas[label].size == expected_size;
            std::optional<Replacement> replacement;
            if (same_area) {
                std::vector<unsigned char> target(cut.size(), 0);
                for (int cell = 0; cell < static_cast<int>(cut.size()); ++cell) {
                    target[cell] = merged.labels[cell] == label;
                }
                const int remaining = input.K - cut_count + static_cast<int>(boundary.cells.size());
                replacement = select_replacement(input, target, cut, remaining, counter,
                                                 deadline, statistics);
            }
            for (int cell : boundary.cells) cut[cell] = 1;
            if (replacement) {
                for (int cell : boundary.cells) cut[cell] = 0;
                for (int cell : replacement->first.cells) cut[cell] = 1;
                for (int cell : replacement->second.cells) cut[cell] = 1;
                cut_count += static_cast<int>(replacement->first.cells.size() +
                    replacement->second.cells.size()) - static_cast<int>(boundary.cells.size());
                statistics.moves.push_back({boundary.cells, std::move(*replacement), skipped});
                // 配置が変わったので、現在の境界を再び短い順に並べる。
                break;
            }
            ++skipped;
        }
    }

    // 従来どおり、最後に1本だけ余れば未選択の乾燥度9から補う。
    if (cut_count + 1 == input.K) {
        for (int cell = 0; cell < input.N * input.N; ++cell) {
            if (!cut[cell] && input.d[cell / input.N][cell % input.N] == 9) {
                cut[cell] = 1;
                ++cut_count;
                break;
            }
        }
    }
    Output output;
    for (int cell = 0; cell < input.N * input.N; ++cell) {
        if (cut[cell]) output.cut_trees.emplace_back(cell / input.N, cell % input.N);
    }
    statistics.final_components = static_cast<int>(counter.analyze(cut).areas.size());
    statistics.elapsed_seconds = std::chrono::duration<double>(Clock::now() - process_start).count();
    if (result_statistics) *result_statistics = std::move(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);
#ifdef LOCAL
    std::cerr.precision(17);
    std::cerr << "{\"passes\":" << statistics.passes
              << ",\"boundaries\":" << statistics.boundaries
              << ",\"candidate_lines\":" << statistics.candidate_lines
              << ",\"evaluated_pairs\":" << statistics.evaluated_pairs
              << ",\"valid_pairs\":" << statistics.valid_pairs
              << ",\"initial_components\":" << statistics.initial_components
              << ",\"final_components\":" << statistics.final_components
              << ",\"elapsed_seconds\":" << statistics.elapsed_seconds << ",\"moves\":[";
    bool first_move = true;
    const auto print_cells = [](const std::vector<int>& cells) {
        for (std::size_t i = 0; i < cells.size(); ++i) {
            if (i) std::cerr << ',';
            std::cerr << cells[i];
        }
    };
    for (const auto& move : statistics.moves) {
        if (!first_move) std::cerr << ',';
        first_move = false;
        const auto& r = move.replacement;
        std::cerr << "{\"removed\":[";
        print_cells(move.removed);
        std::cerr << "],\"added\":[";
        print_cells(r.first.cells);
        std::cerr << ',';
        print_cells(r.second.cells);
        std::cerr << "],\"lengths\":[" << r.first.length << ',' << r.second.length
                  << "],\"starts\":[" << r.first.start << ',' << r.second.start
                  << "],\"ends\":[" << r.first.end << ',' << r.second.end
                  << "],\"value\":" << r.value << ",\"areas\":[";
        for (int k = 0; k < 3; ++k) {
            if (k) std::cerr << ',';
            std::cerr << '[' << r.areas[k].size << ',' << r.areas[k].dryness_sum << ']';
        }
        std::cerr << "],\"skipped_shorter_boundaries\":" << move.skipped_shorter_boundaries << '}';
    }
    std::cerr << "]}\n";
#endif
    return 0;
}