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

• 問題: No.5025 Forest Fire
• ユーザー: bird01
• 提出日時: 2026-10-24 17:20:19
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,933 ms / 2,000 ms
• コード長: 9,945 bytes
• コンパイル時間: 3,192 ms
• コンパイル使用メモリ: 360,336 KB
• 実行使用メモリ: 9,924 KB
• スコア: 140,663,429
• 最終ジャッジ日時: 2026-10-24 17:27:41
• 合計ジャッジ時間: 160,784 ms
• ジャッジサーバーID （参考情報）: judge2_0 / <nil>

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

ソースコード

// 3.
#include <bits/stdc++.h>
using namespace std;

// 仕切りは配列中の並び順で生成する
struct Wall {
  int y, x;
  double angle;
};

const int TRIALS = 100;
const int LIMIT_MS = 1950;
const int MAX_CUT = 100;
const double PI = acos(-1.0);

// 消失確率の和を求める。burn_count 指定時は各マスの焼失回数も記録する
// 雷は木が残っているマスから選び、湿った木に落ちた場合は延焼しない
// cntの有無は記録だけを変える
// tree: 初期の木（位置）, cut: 伐採有無
// 出力の評価値 = (100試行の焼失本数の合計) / 100

double simulate(const vector<int>& d, const vector<vector<int>>& adj,
                const vector<unsigned char>& cut, mt19937& rng,
                vector<int>* burn_count = nullptr) {
  int NN = (int)d.size();
  vector<int> alive;
  alive.reserve(NN);
  for(int p=0; p<NN; p++) {
    if(d[p] > 0 && !cut[p]) alive.push_back(p);
  }
  if(alive.empty()) return 0.0;

  if(burn_count != nullptr) burn_count->assign(NN, 0);
  uniform_int_distribution<int> rnd10(0, 9);
  uniform_int_distribution<int> rnd_tree(0, (int)alive.size() - 1);
  vector<unsigned char> dry(NN, 0);
  vector<int> q(NN);
  long long sum_burned = 0;

  for(int t=0; t<TRIALS; t++) {
    fill(dry.begin(), dry.end(), 0);
    for(int p : alive) dry[p] = rnd10(rng) < d[p];

    int start = alive[rnd_tree(rng)];
    if(!dry[start]) continue;

    int head = 0, tail = 0;
    q[tail++] = start;
    dry[start] = 0;
    while(head < tail) {
      int p = q[head++];
      if(burn_count != nullptr) (*burn_count)[p]++;
      for(int to : adj[p]) {
        if(!dry[to]) continue;
        dry[to] = 0;
        q[tail++] = to;
      }
    }
    sum_burned += tail;
  }
  return (double)sum_burned / TRIALS;
}

// 3×3内での4近傍BFS。対象マスは未伐採として呼び出す
bool need_cut(int y, int x, int N, const vector<unsigned char>& eligible,
              const vector<unsigned char>& cut) {
  bool vis[3][3] = {};
  int qy[9], qx[9], head = 0, tail = 0;
  vis[1][1] = true;
  qy[tail] = y;
  qx[tail] = x;
  tail++;

  const int dy[4] = {-1, 1, 0, 0};
  const int dx[4] = {0, 0, -1, 1};
  while(head < tail) {
    int cy = qy[head], cx = qx[head];
    head++;
    for(int k=0; k<4; k++) {
      int ny = cy + dy[k], nx = cx + dx[k];
      if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
      if(abs(ny-y)>1 || abs(nx-x)>1) continue;
      int p = ny*N + nx;
      if(!eligible[p] || cut[p]) continue;
      int iy = ny-y+1, ix = nx-x+1;
      if(vis[iy][ix]) continue;
      vis[iy][ix] = true;
      qy[tail] = ny;
      qx[tail] = nx;
      tail++;
    }
  }

  for(int dy=-1; dy<=1; dy++) {
    for(int dx=-1; dx<=1; dx++) {
      if(dy==0 && dx==0) continue;
      int ny = y+dy, nx = x+dx;
      if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
      int p = ny*N + nx;
      if(eligible[p] && !cut[p] && !vis[dy+1][dx+1]) return false;
    }
  }
  return true;
}

// 直線上の候補マスを順番に収集する。既存の仕切り・対象外・盤面外で停止
void collect_ray(int y, int x, double dy, double dx, int N,
                 const vector<unsigned char>& eligible,
                 const vector<unsigned char>& cut, vector<int>& candidates) {
  int sy = (dy>0) - (dy<0);
  int sx = (dx>0) - (dx<0);
  double next_y = sy ? 0.5 / abs(dy) : numeric_limits<double>::infinity();
  double next_x = sx ? 0.5 / abs(dx) : numeric_limits<double>::infinity();
  double step_y = sy ? 1.0 / abs(dy) : numeric_limits<double>::infinity();
  double step_x = sx ? 1.0 / abs(dx) : numeric_limits<double>::infinity();

  while(true) {
    if(next_y < next_x) {
      y += sy;
      next_y += step_y;
    } else {
      x += sx;
      next_x += step_x;
    }
    if(y<0 || y>=N || x<0 || x>=N) break;
    int p = y*N + x;
    if(!eligible[p] || cut[p]) break;
    candidates.push_back(p);
  }
}

// 仕切り情報を生成順に再生し、伐採マスを確定する
vector<unsigned char> build_cut(int N, const vector<unsigned char>& eligible,
                                const vector<Wall>& walls) {
  vector<unsigned char> cut(N*N, 0);
  int count = 0;
  for(const Wall& w : walls) {
    if(count >= MAX_CUT) break;
    int start = w.y*N + w.x;
    if(!eligible[start] || cut[start]) continue;

    // 今回の仕切りの候補を、生成ポイント・成長方向・逆方向の順に列挙
    vector<int> candidates = {start};
    double dy = sin(w.angle), dx = cos(w.angle);
    collect_ray(w.y, w.x, dy, dx, N, eligible, cut, candidates);
    collect_ray(w.y, w.x, -dy, -dx, N, eligible, cut, candidates);

    // 伐採枠内の候補を先に仮伐採する（未判定の候補もBFSに反映）
    int end = min((int)candidates.size(), MAX_CUT-count);
    for(int i=0; i<end; i++) cut[candidates[i]] = 1;

    int i = 0;
    for(; i<end; i++) {
      int p = candidates[i];
      // 対象マスだけを一時的に未伐採にしてBFSを実行
      cut[p] = 0;
      if(need_cut(p/N, p%N, N, eligible, cut)) {
        cut[p] = 1;
        count++;
      } else {
        // 外した候補は未伐採のまま。空いた枠に次の候補を仮伐採
        if(end < (int)candidates.size()) {
          cut[candidates[end]] = 1;
          end++;
        }
      }
      if(count >= MAX_CUT) {
        i++;
        break;
      }
    }

    // 100本到達時に、未判定の仮伐採マスを残さない
    for(; i<end; i++) cut[candidates[i]] = 0;
  }
  return cut;
}

int main() {
  auto start_time = chrono::steady_clock::now();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, K;
  cin >> N >> K;
  vector<int> d(N*N, 0);
  for(int i=0; i<N; i++) {
    string s;
    cin >> s;
    for(int j=0; j<N; j++) d[i*N+j] = s[j]-'0';
  }

  vector<vector<int>> adj(N*N);
  const int dy4[4] = {-1,1,0,0};
  const int dx4[4] = {0,0,-1,1};
  for(int y=0; y<N; y++) {
    for(int x=0; x<N; x++) {
      for(int k=0; k<4; k++) {
        int ny = y+dy4[k], nx = x+dx4[k];
        if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
        adj[y*N+x].push_back(ny*N+nx);
      }
    }
  }

  mt19937 rng(random_device{}());
  uniform_real_distribution<double> rnd01(0.0, 1.0);
  uniform_real_distribution<double> rnd_angle(0.0, 2.0*PI);
  vector<unsigned char> no_cut(N*N, 0);

  // 初期盤面の消失確率は一度だけ推定し、以後使い回す
  vector<int> initial_burn;
  simulate(d, adj, no_cut, rng, &initial_burn);
  vector<unsigned char> eligible(N*N, 0);
  vector<int> points;
  for(int p=0; p<N*N; p++) {
    if(d[p]>0 && initial_burn[p]>=25) {
      eligible[p] = 1;
      points.push_back(p);
    }
  }

  // 消失確率0.25以上の木がなければ仕切りを生成できない
  if(points.empty()) {
    cout << 0 << '\n';
    return 0;
  }

  uniform_int_distribution<int> rnd_point(0, (int)points.size()-1);
  auto random_wall = [&]() {
    int p = points[rnd_point(rng)];
    return Wall{p/N, p%N, rnd_angle(rng)};
  };

  // 初期解は仕切り0個
  vector<Wall> current;
  vector<unsigned char> current_cut = no_cut;
  double current_score = simulate(d, adj, current_cut, rng);
  vector<unsigned char> best_cut = current_cut;
  double best_score = current_score;

  while(true) {
    double ms = chrono::duration<double, milli>(
      chrono::steady_clock::now()-start_time).count();
    if(ms >= LIMIT_MS) break;

    // 5種類の近傍を等確率で選択
    int type = uniform_int_distribution<int>(0, 4)(rng);
    if(current.empty() && type != 4) continue;
    vector<Wall> next = current;

    if(type == 0) {
      // 削除・追加
      int idx = uniform_int_distribution<int>(0, (int)next.size()-1)(rng);
      next.erase(next.begin()+idx);
      next.push_back(random_wall());
    } else if(type == 1) {
      // 方向変更
      int idx = uniform_int_distribution<int>(0, (int)next.size()-1)(rng);
      next[idx].angle = rnd_angle(rng);
    } else if(type == 2) {
      // ポイント変更：マンハッタン距離3以内の対象点に移動
      int idx = uniform_int_distribution<int>(0, (int)next.size()-1)(rng);
      vector<int> candidates;
      for(int dy=-3; dy<=3; dy++) {
        for(int dx=-3; dx<=3; dx++) {
          if(abs(dy)+abs(dx)>3 || (dy==0 && dx==0)) continue;
          int ny = next[idx].y+dy, nx = next[idx].x+dx;
          if(ny<0 || ny>=N || nx<0 || nx>=N) continue;
          if(eligible[ny*N+nx]) candidates.push_back(ny*N+nx);
        }
      }
      if(candidates.empty()) continue;
      int p = candidates[uniform_int_distribution<int>(0, (int)candidates.size()-1)(rng)];
      next[idx].y = p/N;
      next[idx].x = p%N;
    } else if(type == 3) {
      // 生成順変更
      int idx = uniform_int_distribution<int>(0, (int)next.size()-1)(rng);
      Wall w = next[idx];
      next.erase(next.begin()+idx);
      int pos = uniform_int_distribution<int>(0, (int)next.size())(rng);
      next.insert(next.begin()+pos, w);
    } else {
      // 単純追加
      next.push_back(random_wall());
    }

    vector<unsigned char> next_cut = build_cut(N, eligible, next);
    double next_score = simulate(d, adj, next_cut, rng);

    // 評価値が小さい方を優先する焼きなまし
    // 指数関数的に開始温度1000から終了温度0.5へ変化
    double progress = min(1.0, ms / LIMIT_MS);
    double temperature = 1000.0 * pow(0.5/1000.0, progress);
    double delta = next_score - current_score;
    if(delta <= 0.0 || rnd01(rng) < exp(-delta/temperature)) {
      current = move(next);
      current_cut = move(next_cut);
      current_score = next_score;
      if(current_score < best_score) {
        best_score = current_score;
        best_cut = current_cut;
      }
    }
  }

  vector<pair<int,int>> answer;
  for(int p=0; p<N*N; p++) {
    if(best_cut[p]) answer.push_back({p/N, p%N});
  }
  cout << answer.size() << '\n';
  for(auto [y,x] : answer) cout << y << ' ' << x << '\n';
  return 0;
}