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

• 問題: No.5025 Forest Fire
• ユーザー: mikuhatsune0831
• 提出日時: 2026-10-24 17:18:27
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 6,337 bytes
• コンパイル時間: 2,224 ms
• コンパイル使用メモリ: 236,808 KB
• 実行使用メモリ: 9,928 KB
• スコア: 74,190,287
• 最終ジャッジ日時: 2026-10-24 17:22:38
• 合計ジャッジ時間: 59,386 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

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

ソースコード

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

namespace firebreak {

struct Problem {
    int n;
    int k;
    std::vector<std::vector<int>> d;
};

using Cell = std::pair<int, int>;
using Priority = std::tuple<int, int, int>;
using DrawIndex = std::function<std::size_t(std::size_t)>;

constexpr int di[] = {-1, 1, 0, 0};
constexpr int dj[] = {0, 0, -1, 1};

template <class NextReal, class BeginRound>
std::size_t draw_unique_max(std::size_t count, NextReal&& next_real,
                            BeginRound&& begin_round) {
    if (count == 0) {
        throw std::runtime_error("Cannot draw from an empty candidate set");
    }
    for (;;) {
        begin_round();
        double maximum = -1.0;
        std::size_t winner = 0;
        bool maximum_is_tied = false;
        for (std::size_t index = 0; index < count; ++index) {
            const double value = next_real();
            if (value > maximum) {
                maximum = value;
                winner = index;
                maximum_is_tied = false;
            } else if (value == maximum) {
                maximum_is_tied = true;
            }
        }
        if (!maximum_is_tied) {
            return winner;
        }
    }
}

class UniformMaxDraw {
public:
    explicit UniformMaxDraw(std::uint64_t first_seed) : next_seed_(first_seed) {}

    std::size_t operator()(std::size_t count) {
        return draw_unique_max(
            count,
            [this] { return distribution_(engine_); },
            [this] {
                // One seed per draw over the tied candidates, including retries.
                engine_.seed(next_seed_++);
                distribution_.reset();
            });
    }

private:
    std::mt19937_64 engine_;
    std::uniform_real_distribution<double> distribution_{0.0, 1.0};
    std::uint64_t next_seed_;
};

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

Problem read_problem(std::istream& in) {
    Problem p{};
    if (!(in >> p.n >> p.k) || p.n <= 0 || p.k < 0) {
        throw std::runtime_error("Invalid N or K");
    }
    p.d.assign(p.n, std::vector<int>(p.n));
    for (int i = 0; i < p.n; ++i) {
        std::string row;
        if (!(in >> row) || row.size() != static_cast<std::size_t>(p.n)) {
            throw std::runtime_error("Invalid grid row");
        }
        for (int j = 0; j < p.n; ++j) {
            if (row[j] < '0' || row[j] > '9') {
                throw std::runtime_error("Invalid dryness value");
            }
            p.d[i][j] = row[j] - '0';
        }
    }
    return p;
}

Priority priority_at(const Problem& p, int i, int j) {
    const int value = p.d[i][j];
    int neighbor_sum = 0;
    int squared_difference_sum = 0;
    for (int direction = 0; direction < 4; ++direction) {
        const int ni = i + di[direction];
        const int nj = j + dj[direction];
        const int neighbor = inside(p.n, ni, nj) ? p.d[ni][nj] : 0;
        neighbor_sum += neighbor;
        const int difference = value - neighbor;
        squared_difference_sum += difference * difference;
    }

    // Compare 4*S and 4*R as integers; this preserves the specified ordering.
    const int four_s = 4 * value + neighbor_sum;
    const int twice_i_offset = 2 * i - (p.n - 1);
    const int twice_j_offset = 2 * j - (p.n - 1);
    const int four_r = twice_i_offset * twice_i_offset
                     + twice_j_offset * twice_j_offset;
    return {-four_s, squared_difference_sum, four_r};
}

std::vector<Cell> select_trees(Problem p, const DrawIndex& draw_index) {
    std::vector<Cell> trees;
    for (int i = 0; i < p.n; ++i) {
        for (int j = 0; j < p.n; ++j) {
            if (p.d[i][j] > 0) {
                trees.emplace_back(i, j);
            }
        }
    }
    if (trees.size() <= static_cast<std::size_t>(p.k)) {
        return trees;
    }

    std::vector<std::vector<Priority>> priorities(
        p.n, std::vector<Priority>(p.n));
    for (int i = 0; i < p.n; ++i) {
        for (int j = 0; j < p.n; ++j) {
            priorities[i][j] = priority_at(p, i, j);
        }
    }

    std::vector<Cell> selected;
    selected.reserve(p.k);
    for (int step = 0; step < p.k; ++step) {
        std::vector<Cell> ties;
        Priority best{};
        for (int i = 0; i < p.n; ++i) {
            for (int j = 0; j < p.n; ++j) {
                if (p.d[i][j] == 0) {
                    continue;
                }
                const Priority& key = priorities[i][j];
                if (ties.empty() || key < best) {
                    best = key;
                    ties.clear();
                    ties.emplace_back(i, j);
                } else if (key == best) {
                    ties.emplace_back(i, j);
                }
            }
        }

        std::size_t index = 0;
        if (ties.size() > 1) {
            index = draw_index(ties.size());
            if (index >= ties.size()) {
                throw std::runtime_error("Tie draw returned an invalid index");
            }
        }
        const auto [i, j] = ties[index];
        selected.emplace_back(i, j);
        p.d[i][j] = 0;
        for (int direction = 0; direction < 4; ++direction) {
            const int ni = i + di[direction];
            const int nj = j + dj[direction];
            if (inside(p.n, ni, nj)) {
                priorities[ni][nj] = priority_at(p, ni, nj);
            }
        }
    }
    return selected;
}

void write_answer(std::ostream& out, const std::vector<Cell>& cells) {
    out << cells.size() << '\n';
    for (const auto& [i, j] : cells) {
        out << i << ' ' << j << '\n';
    }
}

}  // namespace firebreak

#ifndef FIREBREAK_NO_MAIN
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    try {
        auto problem = firebreak::read_problem(std::cin);
        firebreak::UniformMaxDraw draw(1);
        const auto answer = firebreak::select_trees(
            std::move(problem),
            [&draw](std::size_t count) { return draw(count); });
        firebreak::write_answer(std::cout, answer);
        return 0;
    } catch (const std::exception& error) {
        std::cerr << error.what() << '\n';
        return 1;
    }
}
#endif