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

• 問題: No.5025 Forest Fire
• ユーザー: ふらわぁ
• 提出日時: 2026-10-24 17:05:22
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 2,967 bytes
• コンパイル時間: 2,518 ms
• コンパイル使用メモリ: 365,200 KB
• 実行使用メモリ: 9,928 KB
• スコア: 153,541,977
• 最終ジャッジ日時: 2026-10-24 17:06:19
• 合計ジャッジ時間: 56,256 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

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

ソースコード

// cross_var.cpp の d の総和を d^a の総和に置き換えたもの（a は POW_A、コンパイル時に -DPOW_A=1.5 のように指定）。
// 1-indexed の h 行目・w 列目（2 <= h, w <= N-1、端は含めない）の木をすべて伐採する。
// 十字で区切られる 4 つの長方形について d^a の総和 D[0..3]（十字上のマスは含めない）を取り、
// その不偏分散が最小になる (h, w) を選ぶ。同点なら |h-25| + |w-25| が最小のもの。
// 不偏分散 = (4*sum(D^2) - (sum D)^2) / 12 なので、比較は分子 4*sum(D^2) - (sum D)^2（double）で行う。
// 同点は double の厳密な == で判定する（許容誤差は設けていない）。
// それでも決まらない同点は、先に走査した (h, w)（h 昇順、w 昇順）を残す。
#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;

  const double a = POW_A;
  double val[10];
  for (int x = 0; x < 10; x++) val[x] = pow((double)x, 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 bestDist = INT_MAX, bestH = -1, bestW = -1;
  bool tie = false;
  int tieRule = 0;  // 第 2 規則（距離）で選び直した回数（LOCAL 用）
  for (int h = 2; h <= n - 1; h++) {
    for (int w = 2; w <= n - 1; w++) {
      int r = h - 1, c = w - 1;  // 0-indexed の切る行・列
      double D[4] = {rect(0, r, 0, c), rect(0, r, c + 1, n), rect(r + 1, n, 0, c), rect(r + 1, n, c + 1, n)};
      double sum = 0, sq = 0;
      for (double x : D) sum += x, sq += x * x;
      double var = 4 * sq - sum * sum;
      int dist = abs(h - 25) + abs(w - 25);
      if (var < bestVar || (var == bestVar && dist < bestDist)) {
        if (var == bestVar) tieRule++;
        bestVar = var, bestDist = dist, bestH = h, bestW = w;
        tie = false;
      } else if (var == bestVar && dist == bestDist) {
        tie = true;
      }
    }
  }
  (void)tie, (void)tieRule;
#ifdef LOCAL
  if (tie) fprintf(stderr, "TIE h=%d w=%d var=%.17g dist=%d\n", bestH, bestW, bestVar, bestDist);
  fprintf(stderr, "h=%d w=%d var12=%.17g tieRule=%d\n", bestH, bestW, bestVar, tieRule);
#endif

  int r = bestH - 1, c = bestW - 1;
  vector<pair<int, int>> cuts;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if ((i == r || j == c) && d[i][j] != '0') cuts.emplace_back(i, j);
  printf("%d\n", (int)cuts.size());
  for (auto [i, j] : cuts) printf("%d %d\n", i, j);
}