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

• 問題: No.5025 Forest Fire
• ユーザー: occhan
• 提出日時: 2026-10-24 16:23:20
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,705 ms / 2,000 ms
• コード長: 7,658 bytes
• コンパイル時間: 3,250 ms
• コンパイル使用メモリ: 369,668 KB
• 実行使用メモリ: 9,924 KB
• スコア: 146,686,114
• 最終ジャッジ日時: 2026-10-24 16:26:30
• 合計ジャッジ時間: 143,749 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

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

ソースコード

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

static constexpr int MAXN = 50;
static constexpr int MAXV = MAXN * MAXN;
static constexpr int MAIN_SAMPLES = 256;
static constexpr int PAIR_SAMPLES = 64;
static constexpr int TOP = 10;
static constexpr int PAIR_INTERVAL = 20;

int N, K, V;
vector<string> d;
vector<int> trees;

static unsigned char dry[MAIN_SAMPLES][MAXV];
static unsigned char cutCell[MAXV];

static int ord_[MAXV], low_[MAXV], sub_[MAXV], parent_[MAXV];
static int sepSize_[MAXV], compId_[MAXV];
static long long sepSq_[MAXV];
static int compSize_[MAXV];
static int timer_, compCnt_;

static int singlePairSample[PAIR_SAMPLES][MAXV];
static long long totalSingle[MAXV];
static long long pairSingle[MAXV];

static int deg_[MAXV];
static int nbr_[MAXV][4];

void dfsLow(int v, int s, int extraCut, int cid) {
  ord_[v] = low_[v] = timer_++;
  sub_[v] = 1;
  compId_[v] = cid;

  for (int z = 0; z < deg_[v]; ++z) {
    int to = nbr_[v][z];
    if (to == extraCut || cutCell[to] || !dry[s][to]) continue;

    if (ord_[to] == -1) {
      parent_[to] = v;
      dfsLow(to, s, extraCut, cid);
      sub_[v] += sub_[to];
      low_[v] = min(low_[v], low_[to]);

      if (low_[to] >= ord_[v]) {
        sepSize_[v] += sub_[to];
        sepSq_[v] += 1LL * sub_[to] * sub_[to];
      }
    } else if (to != parent_[v]) {
      low_[v] = min(low_[v], ord_[to]);
    }
  }
}

void buildLowlink(int s, int extraCut) {
  fill(ord_, ord_ + V, -1);
  fill(parent_, parent_ + V, -1);
  fill(sepSize_, sepSize_ + V, 0);
  fill(sepSq_, sepSq_ + V, 0LL);

  timer_ = 0;
  compCnt_ = 0;

  for (int start : trees) {
    if (start == extraCut || cutCell[start] || !dry[s][start] || ord_[start] != -1) continue;

    int cid = compCnt_++;
    dfsLow(start, s, extraCut, cid);
    compSize_[cid] = sub_[start];
  }
}

inline int valueOf(int v) {
  if (v < 0 || v >= V || cutCell[v] || ord_[v] == -1) return 0;

  int S = compSize_[compId_[v]];
  int remain = S - 1 - sepSize_[v];

  long long after = sepSq_[v] + 1LL * remain * remain;
  long long before = 1LL * S * S;
  return (int)(before - after);
}

inline int getD(int v) {
  return d[v / N][v % N] - '0';
}

bool singleBetterByMain(int a, int b) {
  if (b == -1) return true;
  if (totalSingle[a] != totalSingle[b]) return totalSingle[a] > totalSingle[b];
  if (getD(a) != getD(b)) return getD(a) > getD(b);
  return a < b;
}

bool singleBetterByPair(int a, int b) {
  if (b == -1) return true;
  if (pairSingle[a] != pairSingle[b]) return pairSingle[a] > pairSingle[b];
  if (getD(a) != getD(b)) return getD(a) > getD(b);
  return a < b;
}

struct PairChoice {
  long long score = LLONG_MIN;
  int a = -1;
  int b = -1;
};

bool pairTieBetter(int a, int b, int ca, int cb) {
  if (ca == -1) return true;

  int da1 = getD(a), da2 = getD(b);
  if (da1 < da2) swap(da1, da2);
  int dc1 = getD(ca), dc2 = getD(cb);
  if (dc1 < dc2) swap(dc1, dc2);

  if (da1 != dc1) return da1 > dc1;
  if (da2 != dc2) return da2 > dc2;

  int a1 = min(a, b), a2 = max(a, b);
  int c1 = min(ca, cb), c2 = max(ca, cb);
  if (a1 != c1) return a1 < c1;
  return a2 < c2;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> N >> K;
  V = N * N;

  d.resize(N);
  for (int i = 0; i < N; ++i) cin >> d[i];

  trees.reserve(V);

  for (int r = 0; r < N; ++r) {
    for (int c = 0; c < N; ++c) {
      int v = r * N + c;
      if (d[r][c] != '0') trees.push_back(v);

      if (r > 0) nbr_[v][deg_[v]++] = v - N;
      if (r + 1 < N) nbr_[v][deg_[v]++] = v + N;
      if (c > 0) nbr_[v][deg_[v]++] = v - 1;
      if (c + 1 < N) nbr_[v][deg_[v]++] = v + 1;
    }
  }

  mt19937 rng(123456789);

  for (int s = 0; s < MAIN_SAMPLES; ++s) {
    for (int v : trees) {
      dry[s][v] = ((int)(rng() % 10) < getD(v));
    }
  }

  vector<int> answer;
  answer.reserve(K);

  int decisionStep = 0;

  while ((int)answer.size() < K) {
    fill(totalSingle, totalSingle + V, 0LL);
    fill(pairSingle, pairSingle + V, 0LL);

    for (int s = 0; s < MAIN_SAMPLES; ++s) {
      buildLowlink(s, -1);

      for (int v : trees) {
        if (cutCell[v]) continue;
        int val = valueOf(v);
        totalSingle[v] += val;

        if (s < PAIR_SAMPLES) {
          singlePairSample[s][v] = val;
          pairSingle[v] += val;
        }
      }
    }

    int bestSingle = -1;
    for (int v : trees) {
      if (!cutCell[v] && singleBetterByMain(v, bestSingle)) bestSingle = v;
    }
    if (bestSingle == -1) break;

    if ((int)answer.size() + 1 >= K) {
      cutCell[bestSingle] = 1;
      answer.push_back(bestSingle);
      break;
    }

    bool tryPair = (decisionStep % PAIR_INTERVAL == 0);
    ++decisionStep;

    if (!tryPair) {
      cutCell[bestSingle] = 1;
      answer.push_back(bestSingle);
      continue;
    }

    vector<int> cand;
    cand.reserve(TOP);
    for (int v : trees) {
      if (!cutCell[v]) cand.push_back(v);
    }

    sort(cand.begin(), cand.end(), [](int a, int b) {
      return singleBetterByMain(a, b);
    });
    if ((int)cand.size() > TOP) cand.resize(TOP);

    if ((int)cand.size() < 2) {
      cutCell[bestSingle] = 1;
      answer.push_back(bestSingle);
      continue;
    }

    int C = (int)cand.size();
    static long long pairScore[TOP][TOP];

    for (int i = 0; i < C; ++i) {
      for (int j = i + 1; j < C; ++j) {
        pairScore[i][j] = pairSingle[cand[i]] + pairSingle[cand[j]];
      }
    }

    for (int s = 0; s < PAIR_SAMPLES; ++s) {
      for (int i = 0; i < C; ++i) {
        int a = cand[i];
        if (!dry[s][a]) continue;

        buildLowlink(s, a);

        for (int j = i + 1; j < C; ++j) {
          int b = cand[j];
          if (!dry[s][b]) continue;

          int afterA = valueOf(b);
          pairScore[i][j] += (long long)afterA - singlePairSample[s][b];
        }
      }
    }

    PairChoice bestPair;
    for (int i = 0; i < C; ++i) {
      for (int j = i + 1; j < C; ++j) {
        long long score = pairScore[i][j];
        int a = cand[i], b = cand[j];

        if (score > bestPair.score ||
            (score == bestPair.score && pairTieBetter(a, b, bestPair.a, bestPair.b))) {
          bestPair.score = score;
          bestPair.a = a;
          bestPair.b = b;
        }
      }
    }

    // 通常の「1本貪欲を2回」の64サンプルでの改善量を計算する。
    long long greedy2Score = pairSingle[bestSingle];
    long long secondScore[MAXV];
    fill(secondScore, secondScore + V, 0LL);

    for (int s = 0; s < PAIR_SAMPLES; ++s) {
      buildLowlink(s, bestSingle);

      for (int v : trees) {
        if (v == bestSingle || cutCell[v]) continue;
        secondScore[v] += valueOf(v);
      }
    }

    int bestSecond = -1;
    for (int v : trees) {
      if (v == bestSingle || cutCell[v]) continue;
      if (bestSecond == -1 ||
          secondScore[v] > secondScore[bestSecond] ||
          (secondScore[v] == secondScore[bestSecond] &&
           (getD(v) > getD(bestSecond) ||
            (getD(v) == getD(bestSecond) && v < bestSecond)))) {
        bestSecond = v;
      }
    }

    if (bestSecond != -1) greedy2Score += secondScore[bestSecond];

    // ペアが通常2手貪欲より3%以上良い場合だけ採用。
    bool usePair =
        bestPair.a != -1 &&
        bestPair.score * 100LL > greedy2Score * 103LL;

    if (usePair) {
      cutCell[bestPair.a] = 1;
      cutCell[bestPair.b] = 1;
      answer.push_back(bestPair.a);
      answer.push_back(bestPair.b);
    } else {
      cutCell[bestSingle] = 1;
      answer.push_back(bestSingle);
    }
  }

  cout << answer.size() << '\n';
  for (int v : answer) {
    cout << v / N << ' ' << v % N << '\n';
  }

  return 0;
}