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

• 問題: No.5025 Forest Fire
• ユーザー: twins_fuyu
• 提出日時: 2026-10-24 17:29:18
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,890 ms / 2,000 ms
• コード長: 8,047 bytes
• コンパイル時間: 4,037 ms
• コンパイル使用メモリ: 371,924 KB
• 実行使用メモリ: 9,928 KB
• スコア: 136,774,603
• 最終ジャッジ日時: 2026-10-24 17:41:51
• 合計ジャッジ時間: 159,384 ms
• ジャッジサーバーID （参考情報）: judge3_0 / <nil>

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using Clock = chrono::steady_clock;

namespace Config {
constexpr double TIME_LIMIT = 1.9; // 秒。入力・前計算・初期評価を含む
constexpr double D_POWER = 2.0;   // 初期配置と移動先の重み d^D_POWER
constexpr double DIAGONAL_PROB = 0.75; // 他の伐採木の斜め隣に移動先を限定する確率
constexpr uint64_t SEED = 0;
constexpr int SAMPLE_COUNT = 50;
constexpr uint64_t SAMPLE_SEED = 0;
constexpr int LOG_INTERVAL = 100;
}

struct Timer {
    Clock::time_point start = Clock::now();
    double elapsed() const { return chrono::duration<double>(Clock::now()-start).count(); }
};

struct Model {
    int N, T;
    vector<int> cell, id, dryness;
    vector<array<int,4>> neighbors;
    vector<uint8_t> samples, active;
    vector<int> queue;

    Model(int n, const vector<string>& board): N(n), id(n*n,-1) {
        for (int y=0; y<N; ++y) for (int x=0; x<N; ++x) {
            int d=board[y][x]-'0';
            if (!d) continue;
            id[y*N+x]=(int)cell.size(); cell.push_back(y*N+x);
            dryness.push_back(d);
        }
        T=(int)cell.size();
        for (int& v:id) if (v<0) v=T;
        active.resize(T+1); queue.resize(T); neighbors.resize(T);
        for (int v=0; v<T; ++v) {
            int y=cell[v]/N, x=cell[v]%N;
            neighbors[v]={
                y>0 ? id[(y-1)*N+x] : T,
                y+1<N ? id[(y+1)*N+x] : T,
                x>0 ? id[y*N+x-1] : T,
                x+1<N ? id[y*N+x+1] : T
            };
        }
    }

    void build() {
        // 乾燥状態を一度だけ生成し、全ての配置の評価で同じ100サンプルを使う。
        // 公式ジャッジの乱数列の再現ではなく、このプログラム独自のサンプル。
        mt19937_64 sample_rng(Config::SAMPLE_SEED);
        uniform_int_distribution<int> draw(0,9);
        samples.resize(size_t(Config::SAMPLE_COUNT)*T);
        for (int s=0; s<Config::SAMPLE_COUNT; ++s)
            for (int v=0; v<T; ++v)
                samples[size_t(s)*T+v]=(draw(sample_rng)<dryness[v]);
    }

    // E = sum_sample sum_component |C|^2 / (SAMPLE_COUNT * N^2)
    // cut[v]=1 は伐採済み。乾燥していて未伐採の木の4近傍連結成分を列挙する。
    // 時間切れの場合は false を返し、result は変更しない。
    bool evaluate(const vector<uint8_t>& cut, double& result,
                  const Timer* timer=nullptr, double limit=0) {
        if (!T) { result=0; return true; }
        uint64_t total=0;
        active[T]=0;
        for (int s=0; s<Config::SAMPLE_COUNT; ++s) {
            if (timer && timer->elapsed()>=limit) return false;
            const uint8_t* sample=samples.data()+size_t(s)*T;
            for (int v=0; v<T; ++v) active[v]=sample[v] && !cut[v];
            for (int v=0; v<T; ++v) {
                if (!active[v]) continue;
                int head=0, tail=0;
                queue[tail++]=v; active[v]=0;
                while (head<tail) {
                    int u=queue[head++];
                    for (int w:neighbors[u]) if (active[w]) {
                        active[w]=0; queue[tail++]=w;
                    }
                }
                total+=uint64_t(tail)*tail;
            }
        }
        result=double(total)/(double(Config::SAMPLE_COUNT)*N*N);
        return true;
    }
};

// 固定の d^power 分布から引き、伐採済みなら引き直す。
// これにより未伐採の木の間で d^power に比例する分布になる。
struct WeightedSampler {
    vector<double> prefix, weight;
    explicit WeightedSampler(const vector<int>& dryness) {
        double sum=0;
        for (int d:dryness) {
            weight.push_back(pow(double(d),Config::D_POWER));
            sum+=weight.back(); prefix.push_back(sum);
        }
    }
    int draw(mt19937_64& rng, const vector<uint8_t>& cut) const {
        for (;;) {
            double r=uniform_real_distribution<double>(0.0,prefix.back())(rng);
            int v=(int)(upper_bound(prefix.begin(),prefix.end(),r)-prefix.begin());
            if (v<(int)cut.size() && !cut[v]) return v;
        }
    }

    int draw_diagonal(mt19937_64& rng, const Model& model,
                      const vector<int>& selected, int slot, const vector<uint8_t>& cut) const {
        vector<uint8_t> seen(model.T,0);
        vector<pair<double,int>> candidates;
        candidates.reserve(4*selected.size());
        double sum=0;
        for (int i=0; i<(int)selected.size(); ++i) {
            if (i==slot) continue; // 移動する伐採木自身は「他の伐採木」に含めない。
            int pos=model.cell[selected[i]], y=pos/model.N, x=pos%model.N;
            for (int dy:{-1,1}) for (int dx:{-1,1}) {
                int ny=y+dy, nx=x+dx;
                if (ny<0 || ny>=model.N || nx<0 || nx>=model.N) continue;
                int v=model.id[ny*model.N+nx];
                if (v==model.T || cut[v] || seen[v]) continue;
                seen[v]=1; // 複数の伐採木に隣接しても重複して重みを加えない。
                sum+=weight[v]; candidates.emplace_back(sum,v);
            }
        }
        if (candidates.empty()) return -1;
        double r=uniform_real_distribution<double>(0.0,sum)(rng);
        auto it=upper_bound(candidates.begin(),candidates.end(),r,
                            [](double x,const auto& entry) { return x<entry.first; });
        return (it==candidates.end() ? candidates.back() : *it).second;
    }
};

int main() {
    Timer timer;
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,K; if (!(cin>>N>>K)) return 0;
    vector<string> board(N); for (auto& s:board) cin>>s;
    Model model(N,board);
    mt19937_64 rng(Config::SEED);
    WeightedSampler sampler(model.dryness);
    vector<uint8_t> cut(model.T,0);
    vector<int> selected;
    int count=min(K,model.T);

    model.build();
    double initial_expected=0;
    model.evaluate(cut,initial_expected); // 伐採前の元盤面
    for (int i=0; i<count; ++i) {
        int v=sampler.draw(rng,cut); cut[v]=1; selected.push_back(v);
    }
    double current=0;
    model.evaluate(cut,current);
    cerr<<fixed<<setprecision(10)
        <<"model_expected_initial="<<initial_expected<<'\n'
        <<"model_expected_start="<<current<<'\n';

    uint64_t iterations=0, accepted=0;
    if (count>0 && count<model.T) {
        uniform_int_distribution<int> choose_slot(0,count-1);
        bernoulli_distribution choose_diagonal(Config::DIAGONAL_PROB);
        while (timer.elapsed()<Config::TIME_LIMIT) {
            int slot=choose_slot(rng), old=selected[slot];
            // old もまだ伐採済みにしておくことで、同じ場所への移動を除外する。
            int next=choose_diagonal(rng)
                ? sampler.draw_diagonal(rng,model,selected,slot,cut)
                : sampler.draw(rng,cut);
            if (next<0) continue; // 限定された候補がなければ、この試行をスキップ。
            cut[old]=0; cut[next]=1;
            double candidate=0;
            bool complete=model.evaluate(cut,candidate,&timer,Config::TIME_LIMIT);
            if (!complete) { cut[old]=1; cut[next]=0; break; }
            ++iterations;
            if (candidate<current) {
                selected[slot]=next; current=candidate; ++accepted;
            } else {
                cut[old]=1; cut[next]=0;
            }
            if (iterations%Config::LOG_INTERVAL==0)
                cerr<<"iteration="<<iterations<<" model_expected="<<current
                    <<" accepted="<<accepted<<" elapsed="<<timer.elapsed()<<'\n';
        }
    }

    cout<<count<<'\n';
    for (int v:selected) cout<<model.cell[v]/N<<' '<<model.cell[v]%N<<'\n';
    // 採用時の評価を保持しているため、最終盤面を再計算する必要はない。
    cerr<<"model_expected_final="<<current<<'\n'
        <<"iterations="<<iterations<<" accepted="<<accepted
        <<" elapsed="<<timer.elapsed()<<'\n';
    return 0;
}