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

• 問題: No.5025 Forest Fire
• ユーザー: kαmμ
• 提出日時: 2026-10-24 17:46:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 17,908 bytes
• コンパイル時間: 3,175 ms
• コンパイル使用メモリ: 366,232 KB
• 実行使用メモリ: 9,928 KB
• スコア: 42,672,236
• 最終ジャッジ日時: 2026-10-24 17:50:33
• 合計ジャッジ時間: 129,630 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

ファイルパターン	結果
other	AC * 20 WA * 30

ソースコード

// #define ALL_DIST

/******************************************
 * ↓↓↓↓↓↓↓↓↓↓↓↓↓ my library ↓↓↓↓↓↓↓↓↓↓↓↓↓ *
 * https://github.com/googologyFan/kammyu *
 ******************************************/

#include <bits/stdc++.h>

#ifndef KAMMYU_CONSTANTS
#define KAMMYU_CONSTANTS

#include <limits>

namespace kammyu
{
  namespace infinities
  {
    constexpr int inf = std::numeric_limits<int>::max();
    constexpr int _inf = std::numeric_limits<int>::min();
    constexpr long long INF = std::numeric_limits<long long>::max();
    constexpr long long _INF = std::numeric_limits<long long>::min();
  }; // namespace infinities
  namespace modulos
  {
    constexpr int Smod = 998244353;
    constexpr int Bmod = 1000000007;
  }; // namespace modulos
}; // namespace kammyu

#endif // KAMMYU_CONSTANTS

#ifndef KAMMYU_INPUT
#define KAMMYU_INPUT

#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

namespace kammyu
{
  namespace input
  {
    template <typename T1, typename T2>
    std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p)
    {
      return is >> p.first >> p.second;
    }

    template <typename T>
    std::istream& operator>>(std::istream& is, std::vector<T>& v)
    {
      for (T& x : v)
        is >> x;
      return is;
    }

    template <typename T>
    void inp_arr(std::vector<T>& v)
    {
      for (T& i : v)
        std::cin >> i;
    }
    template <typename T1, typename T2>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i];
    }
    template <typename T1, typename T2, typename T3>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2, std::vector<T3>& v3)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i] >> v3[i];
    }
    template <typename T1, typename T2, typename T3, typename T4>
    void inp_arr(std::vector<T1>& v1, std::vector<T2>& v2, std::vector<T3>& v3, std::vector<T4>& v4)
    {
      for (int i = 0; i < (int)v1.size(); i++)
        std::cin >> v1[i] >> v2[i] >> v3[i] >> v4[i];
    }
    template <typename T>
    void inp_arr(std::vector<std::vector<T>>& v)
    {
      for (std::vector<T>& i : v)
        for (T& j : i)
          std::cin >> j;
    }
  }; // namespace input
}; // namespace kammyu

#endif // KAMMYU_INPUT

#ifndef KAMMYU_OUTPUT
#define KAMMYU_OUTPUT

#include <iostream>
#include <ostream>
#include <vector>

namespace kammyu
{
  namespace output
  {
    std::ostream& operator<<(std::ostream& os, const std::vector<std::string>& v)
    {
      for (const std::string& x : v)
        os << x << "\n";
      return os;
    }
    template <typename T>
    std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
    {
      for (const T& x : v)
        os << x << ' ';
      return os;
    }
    template <typename T>
    std::ostream& operator<<(std::ostream& os, const std::vector<std::vector<T>>& v)
    {
      for (const std::vector<T>& x : v)
        os << x << '\n';
      return os;
    }

    void yes(bool o = false)
    {
      if (o)
        std::cout << "Yes";
      else
        std::cout << "Yes" << std::endl;
    }
    void no(bool o = false)
    {
      if (o)
        std::cout << "No";
      else
        std::cout << "No" << std::endl;
    }
    void yn(bool b, bool o = false)
    {
      if (b)
        yes(o);
      else
        no(o);
    }
  }; // namespace output
}; // namespace kammyu

#endif // KAMMYU_OUTPUT

#ifndef KAMMYU_POINT
#define KAMMYU_POINT

#include <iostream>
#include <tuple>
#include <vector>

namespace kammyu
{
  namespace point
  {
    struct P
    {
    private:
      using ll = long long;

    public:
      P() { P(0, 0); }
      P(ll _i, ll _j) : i(_i), j(_j) {}
      ll i, j;
      bool operator==(const P& p) const { return i == p.i && j == p.j; }
      bool operator!=(const P& p) const { return !(*this == p); }
      bool operator<(const P& other) const { return std::tie(i, j) < std::tie(other.i, other.j); }
      bool operator>(const P& other) const { return std::tie(i, j) > std::tie(other.i, other.j); }
      P operator+(const P& other) const { return P(i + other.i, j + other.j); }
      P operator-(const P& other) const { return P(i - other.i, j - other.j); }
      P operator*(const int& other) const { return P(i * other, j * other); }
      P operator*(const ll& other) const { return P(i * other, j * other); }
      P operator*(const P& other) const { return P(i * other.i, j * other.j); }
      P operator*(const double& other) const { return P(i * other, j * other); }
      P operator/(const ll& scaler) const { return P(i / scaler, j / scaler); }
      P operator/(const double& scaler) const { return P(i / scaler, j / scaler); }
      P operator+=(const P& p) { return *this = *this + p; }
      P operator-=(const P& p) { return *this = *this - p; }
      P operator*=(const ll& p) { return *this = *this * p; }
      friend std::ostream& operator<<(std::ostream& os, const P& p) { return os << p.i << " " << p.j; }
      friend std::istream& operator>>(std::istream& is, P& p) { return is >> p.i >> p.j; }
      bool out_of_bounds(ll size) const { return i < 0 || j < 0 || i >= size || j >= size; }
      bool out_of_bounds(ll H, ll W) const { return i < 0 || j < 0 || i >= H || j >= W; }
      P& operator--()
      {
        --i, --j;
        return *this;
      }
      P operator--(int)
      {
        P p = *this;
        --(*this);
        return p;
      }
      void swap()
      {
        std::swap(i, j);
      }
      ll distEucSq() const { return i * i + j * j; }
      ll distManh() const { return abs(i) + abs(j); }

      P rot45L() const { return P(i - j, i + j); }
      P rot45R() const { return P(-(i + j), i - j); }

      // bool argcomp(const P& o) const
      // {
      //   ;
      // }
    };

    using piP = std::pair<int, P>;
    using pPP = std::pair<P, P>;
    using vP = std::vector<P>;
    using vpiP = std::vector<piP>;
    using vpPP = std::vector<pPP>;
    using vvP = std::vector<std::vector<P>>;
    using vvpiP = std::vector<std::vector<piP>>;
    const vP around4({P(0, 1), P(1, 0), P(0, -1), P(-1, 0)});
    const vP around8({P(0, 1), P(1, 1), P(1, 0), P(1, -1), P(0, -1), P(-1, -1), P(-1, 0), P(-1, 1)});
  }; // namespace point
}; // namespace kammyu

#endif // KAMMYU_POINT

#ifndef KAMMYU_UTILS
#define KAMMYU_UTILS

#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, s, e) for (int i = (s); i < (e); ++i)
#define reep(i, n) for (int i = 0; i <= (n); ++i)
#define reepp(i, s, e) for (int i = (s); i <= (e); ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrepp(i, s, e) for (int i = (e - 1); i >= s; --i)
#define sign(f) (f == 0 ? 0 : ((f) > 0) * 2 - 1)

#define pqueue priority_queue

namespace kammyu
{

  namespace utils
  {
    template <typename T1, typename T2>
    bool chmax(T1& m, const T2& val)
    {
      if (m < val)
      {
        m = val;
        return true;
      }
      return false;
    }
    template <typename T1, typename T2>
    bool chmin(T1& m, const T2& val)
    {
      if (m > val)
      {
        m = val;
        return true;
      }
      return false;
    }

    using ll = long long;
    using pii = std::pair<int, int>;
    using piii = std::pair<int, pii>;
    using si = std::set<int>;
    using vi = std::vector<int>;
    using vpii = std::vector<pii>;
    using vpiii = std::vector<piii>;
    using vvi = std::vector<std::vector<int>>;
    using vvpii = std::vector<std::vector<pii>>;
    using vvvi = std::vector<vvi>;
    using vvvvi = std::vector<vvvi>;

    using vb = std::vector<bool>;
    using vvb = std::vector<vb>;
    using pli = std::pair<ll, int>;
    using plii = std::pair<pli, int>;
    using vpli = std::vector<pli>;
    using vvpli = std::vector<std::vector<pli>>;

    using pll = std::pair<ll, ll>;
    using plll = std::pair<pll, ll>;
    using vl = std::vector<ll>;
    using vpll = std::vector<pll>;
    using vvl = std::vector<std::vector<ll>>;
    using vvpll = std::vector<std::vector<pll>>;
    using vvvl = std::vector<vvl>;
    using vvvvl = std::vector<vvvl>;

    using vsi = std::vector<std::set<int>>;

    using vs = std::vector<std::string>;
    template <typename T>
    using vv = std::vector<std::vector<T>>;

    template <typename T>
    using min_pqueue = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    template <typename T>
    using max_pqueue = std::priority_queue<T>;

    template <typename T1, typename T2>
    std::pair<T1, T2> operator+(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b)
    {
      return std::make_pair(a.first + b.first, a.second + b.second);
    }
    template <typename T1, typename T2>
    std::pair<T1, T2> operator-(const std::pair<T1, T2>& a, const std::pair<T1, T2>& b)
    {
      return std::make_pair(a.first - b.first, a.second - b.second);
    }

    template <typename T>
    void sort(std::vector<T>& v)
    {
      std::sort(all(v));
    }

    vi str2vi(const std::string& s, char first_char = 'a')
    {
      vi res(s.size());
      rep(i, s.size()) res[i] = s[i] - first_char;
      return res;
    }

    template <typename T>
    T sum(const std::vector<T>& vec)
    {
      T res = T();
      for (const T& val : vec)
        res = res + val;
      return res;
    }
    template <typename T>
    T min(const std::vector<T>& vec, T init)
    {
      T res = init;
      for (const T& val : vec)
        if (val < res)
          res = val;
      return res;
    }
    template <typename T>
    T max(const std::vector<T>& vec, T init)
    {
      T res = init;
      for (const T& val : vec)
        if (val > res)
          res = val;
      return res;
    }

  }; // namespace utils
}; // namespace kammyu

#endif // KAMMYU_UTILS


using namespace kammyu::utils;
using namespace kammyu::input;
using namespace kammyu::output;
using namespace kammyu::point;

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

  MAIN();

  return 0;
}

using namespace std;
void solve();
void precalc();
void MAIN()
{
  precalc();
  int T = 1;
  // cin >> T;
  while (T--)
    solve();

  return;
}

// using namespace kammyu::infinities;
// using namespace kammyu::modulos;
const int N = 50, K = 100;
int d[N][N];
int dist[N * N][N * N];
int dec(P p)
{
  return p.i * N + p.j;
}
void precalc()
{
  int n, k;
  cin >> n >> k;
  char c;
  rep(i, n) rep(j, n) cin >> c, d[i][j] = c - '0';

#ifdef ALL_DIST
  rep(_i, n) rep(_j, n)
  {
    P s(_i, _j);
    min_pqueue<piP> que;
    rep(i, n) rep(j, n) dist[dec(s)][i * N + j] = 1e9;
    dist[dec(s)][dec(s)] = d[s.i][s.j];
    que.emplace(d[s.i][s.j], s);
    while (!que.empty())
    {
      auto [di, p] = que.top();
      que.pop();
      if (dist[dec(s)][dec(p)] < di)
        continue;
      for (P dp : around4)
      {
        P np = p + dp;
        if (np.out_of_bounds(n))
          continue;
        int nd = di + d[np.i][np.j];
        if (chmin(dist[dec(s)][dec(np)], nd))
          que.emplace(nd, np);
      }
    }
  }
#endif

  return;
}

//? 取り敢えず制約から $M=K=100$ でよさげ
//? 焼くかぁと思うなどしたが
//? どう解釈しようかね～
//? adhoc解を探すなど
//? まあなんか6以上の連結成分を分割するのは難しそう
//? 5以下のマスをdで重み付けした乱択でやってみるか
struct solver1
{
  set<P> ans;
  void run()
  {
    vP cand;
    rep(i, N) rep(j, N) if (d[i][j] != 0 && d[i][j] <= 5) rep(_, d[i][j]) cand.push_back(P(i, j));
    int C = cand.size();
    vi ord(C);
    rep(i, C) ord[i] = i;
    rep(i, K) swap(ord[i], ord[rand() % C]);

    for (int i : ord)
    {
      ans.insert(cand[i]);
      if (ans.size() == K)
        break;
    }
  }
  void output()
  {
    cout << ans.size() << "\n";
    for (auto [i, j] : ans)
      cout << i << " " << j << "\n";
  }
};

//? 6以上のマスのみを分割しようかなぁ
//? K-meansみたいなことできるかな
//? いくつか i+j が偶数になるようにcenterを求めて，最寄りのcenterまでの距離が複数あってそれらが同じところを伐採
struct solver2
{
  set<P> ans;

  vP Kmeans(const vP points, int k)
  {
    int n = points.size();
    vP centers;
    rep(i, k) centers.push_back(points[rand() % n]);
    rep(iter, 100)
    {
      vector<vector<P>> clusters(k);
      for (auto p : points)
      {
        int best = 0;
        int di = 1e9;
        rep(i, k) if (chmin(di, dist[dec(p)][dec(centers[i])]))
            best = i;
        clusters[best].push_back(p);
      }
      rep(i, k)
      {
        int siz = clusters[i].size();
        if (siz == 0)
          continue;
        P sum(0, 0);
        for (auto p : clusters[i])
          sum += p;
        centers[i] = sum / (ll)siz;
      }
    }
    return centers;
  }
  void run()
  {
    vP d_weighted;
    rep(i, N) rep(j, N) rep(_, d[i][j]) d_weighted.push_back(P(i, j));
    auto centers = Kmeans(d_weighted, 7);
    max_pqueue<pair<int, P>> que;
    vvi di(N, vi(N, 1e9));
    rep(i, N) rep(j, N) if (d[i][j] != 0)
    {
      for (P c : centers)
        chmin(di[i][j], dist[i * N + j][dec(c)]);
      que.emplace(di[i][j] * d[i][j], P(i, j));
    }
    // vvi avo(N, vi(N, 0));
    while (!que.empty())
    {
      auto [dis, p] = que.top();
      que.pop();

      int above = 0;
      for (P dp : around4)
      {
        P np = p + dp;
        if (np.out_of_bounds(N) ||
            di[np.i][np.j] >= dis)
          above++;
      }
      // avo[p.i][p.j] = above;
      if (above >= 2)
        continue;
      ans.insert(p);
      if (ans.size() == K)
        break;
    }
    // cerr << avo << endl;
  }
  void output()
  {
    cout << ans.size() << "\n";
    for (auto [i, j] : ans)
      cout << i << " " << j << "\n";
  }
};

//? 何回かシミュレーションして、8~10%以上高い所の連結成分を分ける
//? 分けるのは，なにがいいかな
//? Kmeansで何個か点を選んでやるか
#include <atcoder/dsu>
using ld = long double;
struct solver3
{
  set<P> ans;

  vv<ld> simulate(int ms)
  {
    vv<ld> result(N, vector<ld>(N, 0));

    vv<char> cut(N, vector<char>(N, false));
    for (P p : ans)
      cut[p.i][p.j] = true;

    auto start = std::chrono::system_clock::now();
    int iter = 0;
    while (true)
    {
      if (std::chrono::system_clock::now() - start > std::chrono::milliseconds(ms))
        break;
      vv<char> dry(N, vector<char>(N, false));
      rep(i, N) rep(j, N) if (!cut[i][j] && rand() % 10 < d[i][j]) dry[i][j] = true;

      atcoder::dsu uf(N * N);
      rep(i, N) rep(j, N) if (dry[i][j])
      {
        for (P dp : around4)
        {
          P np = P(i, j) + dp;
          if (np.out_of_bounds(N) || !dry[np.i][np.j])
            continue;
          uf.merge(dec(P(i, j)), dec(np));
        }
      }

      rep(i, N) rep(j, N) if (dry[i][j]) result[i][j] += (ld)uf.size(i * N + j) / (N * N);
      iter++;
    }
    cerr << "simulation iter = " << iter << endl;
    rep(i, N) rep(j, N) result[i][j] /= iter;

    return result;
  }
  vP Kmeans(const vv<ld> weight, int k)
  {
    vP centers;
    rep(i, k) centers.push_back(P(rand() % N, rand() % N));
    rep(iter, 100)
    {
      vector<vector<P>> clusters(k);
      rep(i, N) rep(j, N)
      {
        P p(i, j);
        int best = 0;
        int di = 1e9;
        rep(i, k) if (chmin(di, dist[dec(p)][dec(centers[i])]))
            best = i;
        clusters[best].push_back(p);
      }
      rep(i, k)
      {
        int siz = clusters[i].size();
        if (siz == 0)
          continue;
        P sum(0, 0);
        double Wsum = 0;
        for (auto p : clusters[i])
          sum += p * (double)weight[p.i][p.j], Wsum += weight[p.i][p.j];
        centers[i] = sum / Wsum;
      }
    }
    rep(i, k) if (centers[i].distManh() & 1)
    {
      int r = rand() % 4;
      if (r == 0)
        centers[i].i++;
      else if (r == 1)
        centers[i].i--;
      else if (r == 2)
        centers[i].j++;
      else
        centers[i].j--;
    }
    return centers;
  }
  void run()
  {
    auto weight = simulate(900);
    // for (P c : centers)
    //   cerr << c << endl;
    double best = N * N;
    set<P> best_ans;
    rep(_, 10)
    {
      ans.clear();
      vP centers = Kmeans(weight, 15);
      max_pqueue<pair<ld, P>> que;
      rep(i, N) rep(j, N)
      {
        P p(i, j);
        int dist = 1e9;
        int cnt = 0;
        for (P c : centers)
        {
          int d = (p - c).distManh();
          if (chmin(dist, d))
            cnt = 1, dist = d;
          else if (d == dist)
            cnt++;
        }
        if (cnt >= 2)
        {
          double w = 0;
          int c = 0;
          reepp(i, -2, 2) reepp(j, -2, 2)
          {
            P np = p + P(i, j);
            if (np.out_of_bounds(N))
              continue;
            w += weight[np.i][np.j];
          }
          que.emplace(w / c, p);
        }
      }
      while (!que.empty())
      {
        auto [di, p] = que.top();
        que.pop();
        ans.insert(p);
        if (ans.size() == K)
          break;
      }
      auto res = simulate(100);
      double score = 0;
      rep(i, N) rep(j, N) score += res[i][j];
      if (chmin(best, score))
        best_ans = ans;
    }
    ans = best_ans;
  }
  void output()
  {
    cout << ans.size() << "\n";
    for (auto [i, j] : ans)
      cout << i << " " << j << "\n";
  }
};

//? 各マスに $10-d_i$ の重みをつけて、最小費用流する？
//? 適当に100点ずつ Source と Drain を設けて...

void solve()
{
  solver3 sol;
  sol.run();
  sol.output();

  return;
}