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

• 問題: No.5025 Forest Fire
• ユーザー: ふらわぁ
• 提出日時: 2026-10-24 17:18:28
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 5,712 bytes
• コンパイル時間: 4,281 ms
• コンパイル使用メモリ: 373,804 KB
• 実行使用メモリ: 9,924 KB
• スコア: 155,322,324
• 最終ジャッジ日時: 2026-10-24 17:22:46
• 合計ジャッジ時間: 59,744 ms
• ジャッジサーバーID （参考情報）: judge3_0 / <nil>

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

ソースコード

// 1 本の列（または行）を全部切り、その両側で別々の行（または列）を切る。d^a (a=POW_A) の総和の不偏分散が小さい方を採用。
// 型 0（列型）: w 列目を全部切り、左側（w 列目より左）で h_L 行目、右側で h_R 行目の木を切る。
//   4 つの長方形: 左上 (行 < h_L, 列 < w)、左下 (行 > h_L, 列 < w)、右上 (行 < h_R, 列 > w)、右下 (行 > h_R, 列 > w)。
//   同点規則の値: |h_R-25| + |h_L-25| + 2*|w-25|
// 型 1（行型）: h 行目を全部切り、上側（h 行目より上）で w_U 列目、下側で w_D 列目の木を切る。
//   4 つの長方形: 左上 (行 < h, 列 < w_U)、右上 (行 < h, 列 > w_U)、左下 (行 > h, 列 < w_D)、右下 (行 > h, 列 > w_D)。
//   同点規則の値: |w_U-25| + |w_D-25| + 2*|h-25|
// h, w, h_L, h_R, w_U, w_D はすべて 1-indexed の 2..N-1（端は含めない）。h_L = h_R、w_U = w_D も含める。
// 各長方形の d^a の総和（切るマスは含めない）D[0..3] の不偏分散 = (4*sum(D^2) - (sum D)^2) / 12 なので、
// 比較は分子 4*sum(D^2) - (sum D)^2（double）で行う。D の順序は両型とも {左上, 右上, 左下, 右下}。
// 選び方: 分散が小さい方。同じなら同点規則の値が小さい方（型をまたいでも同じ比較）。それでも同じなら先に走査した方
// （型 0 → 型 1、各型内は 1 つ目のパラメータ昇順、2 つ目、3 つ目の順）を残す。同点は double の厳密な == で判定する。
// 最後に、切った本数が K に満たない分を、まだ切っていない木から乾燥度 d が高い順に切る
// （d が同じ木は行優先の走査順で先のもの）。
#include <bits/stdc++.h>
using namespace std;

#ifndef POW_A
#define POW_A 3.8
#endif

int main() {
  int n, k;
  cin >> n >> k;
  vector<string> d(n);
  for (auto &row : d) cin >> row;

  double val[10];
  for (int x = 0; x < 10; x++) val[x] = pow((double)x, POW_A);  // d=0 のマスは 0 になる

  // 累積和 S[i][j] = d^a の d[0..i-1][0..j-1] 上での総和
  vector<vector<double>> S(n + 1, vector<double>(n + 1, 0.0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) S[i + 1][j + 1] = S[i][j + 1] + S[i + 1][j] - S[i][j] + val[d[i][j] - '0'];
  auto rect = [&](int i0, int i1, int j0, int j1) {  // 行 [i0,i1) 列 [j0,j1)
    return S[i1][j1] - S[i0][j1] - S[i1][j0] + S[i0][j0];
  };

  double bestVar = DBL_MAX;
  int bestMetric = INT_MAX, bestType = -1, bp0 = -1, bp1 = -1, bp2 = -1;
  int tieCount = 0;  // 分散も同点規則の値も同じだった回数（LOCAL 用）
  auto consider = [&](const double D[4], int metric, int type, int p0, int p1, int p2) {
    double sum = 0, sq = 0;
    for (int t = 0; t < 4; t++) sum += D[t], sq += D[t] * D[t];
    double var = 4 * sq - sum * sum;
    if (var < bestVar || (var == bestVar && metric < bestMetric)) {
      bestVar = var, bestMetric = metric, bestType = type, bp0 = p0, bp1 = p1, bp2 = p2;
      tieCount = 0;
    } else if (var == bestVar && metric == bestMetric) {
      tieCount++;
#ifdef LOCAL
      fprintf(stderr, "TIED type=%d p=%d,%d,%d with best type=%d p=%d,%d,%d\n", type, p0, p1, p2, bestType, bp0, bp1, bp2);
#endif
    }
  };

  // 型 0: p0 = w, p1 = h_L, p2 = h_R
  for (int w = 2; w <= n - 1; w++) {
    int c = w - 1;
    for (int hL = 2; hL <= n - 1; hL++) {
      int rL = hL - 1;
      double UL = rect(0, rL, 0, c), LL = rect(rL + 1, n, 0, c);
      for (int hR = 2; hR <= n - 1; hR++) {
        int rR = hR - 1;
        double D[4] = {UL, rect(0, rR, c + 1, n), LL, rect(rR + 1, n, c + 1, n)};
        consider(D, abs(hR - 25) + abs(hL - 25) + 2 * abs(w - 25), 0, w, hL, hR);
      }
    }
  }
  // 型 1: p0 = h, p1 = w_U, p2 = w_D
  for (int h = 2; h <= n - 1; h++) {
    int r = h - 1;
    for (int wU = 2; wU <= n - 1; wU++) {
      int cU = wU - 1;
      double UL = rect(0, r, 0, cU), UR = rect(0, r, cU + 1, n);
      for (int wD = 2; wD <= n - 1; wD++) {
        int cD = wD - 1;
        double D[4] = {UL, UR, rect(r + 1, n, 0, cD), rect(r + 1, n, cD + 1, n)};
        consider(D, abs(wU - 25) + abs(wD - 25) + 2 * abs(h - 25), 1, h, wU, wD);
      }
    }
  }

  // 切るマス（木のあるマスだけ）
  vector<vector<char>> cut(n, vector<char>(n, 0));
  vector<pair<int, int>> cuts;
  auto add = [&](int i, int j) {
    if (d[i][j] != '0' && !cut[i][j]) cut[i][j] = 1, cuts.emplace_back(i, j);
  };
  if (bestType == 0) {
    int c = bp0 - 1, rL = bp1 - 1, rR = bp2 - 1;
    for (int i = 0; i < n; i++) add(i, c);
    for (int j = 0; j < c; j++) add(rL, j);
    for (int j = c + 1; j < n; j++) add(rR, j);
  } else {
    int r = bp0 - 1, cU = bp1 - 1, cD = bp2 - 1;
    for (int j = 0; j < n; j++) add(r, j);
    for (int i = 0; i < r; i++) add(i, cU);
    for (int i = r + 1; i < n; i++) add(i, cD);
  }
  int m0 = cuts.size();

  // 余った本数を、まだ切っていない木から乾燥度が高い順に（同じ d は行優先の走査順）
  vector<pair<int, int>> rest;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (d[i][j] != '0' && !cut[i][j]) rest.emplace_back(i, j);
  stable_sort(rest.begin(), rest.end(), [&](const pair<int, int> &a, const pair<int, int> &b) { return d[a.first][a.second] > d[b.first][b.second]; });
  for (int t = 0; t < (int)rest.size() && (int)cuts.size() < k; t++) cuts.push_back(rest[t]);

  (void)m0;
#ifdef LOCAL
  fprintf(stderr, "type=%d p=%d,%d,%d var12=%.17g metric=%d struct=%d tie=%d\n", bestType, bp0, bp1, bp2, bestVar, bestMetric, m0, tieCount);
#endif

  printf("%d\n", (int)cuts.size());
  for (auto [i, j] : cuts) printf("%d %d\n", i, j);
}