#1195074 (D) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: allegrogiken
• 提出日時: 2026-10-24 16:41:16
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 5 ms / 2,000 ms
• コード長: 3,930 bytes
• コンパイル時間: 4,329 ms
• コンパイル使用メモリ: 213,796 KB
• 実行使用メモリ: 9,924 KB
• スコア: 72,706,317
• 最終ジャッジ日時: 2026-10-24 16:42:16
• 合計ジャッジ時間: 59,892 ms
• ジャッジサーバーID （参考情報）: judge4_0 / <nil>

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

ソースコード

void main() { runSolver(); }

// ---------------------------------------------

void problem() {
  auto seed = 983_741_243;
  auto RND = Xorshift(seed);
  enum long INF = long.max / 3;
  enum int BIG = 2 ^^ 20;

  auto StartTime = MonoTime.currTime();
  bool elapsed(int ms) { return (ms <= (MonoTime.currTime() - StartTime).total!"msecs"); }

  int TIME_LIMIT = 1900;
  bool reachedTimeLimit() { return elapsed(TIME_LIMIT); }
  
  int N = scan!int;
  int K = scan!int;
  int[][] G = scan!string(N).map!(s => s.map!(c => (c - '0').to!int).array).array;
  int[] GJ = G.joiner.array;
  
  int id(int r, int c) { return r*N + c; }
  int[][] graph = new int[][](N^^2, 0);
  foreach(r; 0..N) foreach(c; 0..N) {
    if (r > 0) graph[id(r, c)] ~= id(r - 1, c);
    if (c > 0) graph[id(r, c)] ~= id(r, c - 1);
    if (r < N - 1) graph[id(r, c)] ~= id(r + 1, c);
    if (c < N - 1) graph[id(r, c)] ~= id(r, c + 1);
  }

  bool valid(int r, int c) {
    return min(r, c) >= 0 && max(r, c) < N;
  }

  int wrapped(int r, int c) {
    if (valid(r, c)) return G[r][c];
    return 0;
  }

  int[] around4(int node) {
    auto r = node / N;
    auto c = node % N;

    int[] ret;
    ret ~= wrapped(r - 1, c);
    ret ~= wrapped(r, c - 1);
    ret ~= wrapped(r + 1, c);
    ret ~= wrapped(r, c + 1);
    return ret.sort!"a > b".array;
  }

  int[] around4X(int node) {
    auto r = node / N;
    auto c = node % N;

    int[] ret;
    ret ~= wrapped(r - 1, c - 1);
    ret ~= wrapped(r + 1, c - 1);
    ret ~= wrapped(r - 1, c + 1);
    ret ~= wrapped(r + 1, c + 1);
    return ret.sort!"a > b".array;
  }
  
  int cellScore(int node) {
    auto p = around4(node);
    auto x = around4X(node);

    int ret;
    ret += p[0] * (p[1] - p[2]);
    ret *= x[2];
    return ret * GJ[node];
  }

  auto nodes = iota(N ^^ 2).filter!(i => GJ[i] > 0).map!(i => [i, cellScore(i)]).array.sort!"a[1] > b[1]";
  writeln(min(K, nodes.length));
  foreach(n; nodes[0..min($, K)].map!"a[0]") {
    writefln("%s %s", n / N, n % N);
  }
}

// ----------------------------------------------

import std;
import core.bitop;
import core.memory : GC;
string scan(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
T scan(T)(){ return scan.to!T; }
T[] scan(T)(long n){ return n.iota.map!(i => scan!T()).array; }
void deb(T ...)(lazy T t){ debug { stderr.write("# "); stderr.writeln(t); }}
void debf(T ...)(lazy T t){ debug { stderr.write("# "); stderr.writefln(t); }}
// void deb(T ...)(T t){ debug {  }}
T[] divisors(T)(T n) { T[] ret; for (T i = 1; i * i <= n; i++) { if (n % i == 0) { ret ~= i; if (i * i != n) ret ~= n / i; } } return ret.sort.array; }
bool chmin(T)(ref T a, T b) { if (b < a) { a = b; return true; } else return false; }
bool chmax(T)(ref T a, T b) { if (b > a) { a = b; return true; } else return false; }
string charSort(alias S = "a < b")(string s) { return (cast(char[])((cast(byte[])s).sort!S.array)).to!string; }
ulong comb(ulong a, ulong b) { if (b == 0) {return 1;}else{return comb(a - 1, b - 1) * a / b;}}
string toAnswerString(R)(R r) { return r.map!"a.to!string".joiner(" ").array.to!string; }
void outputForAtCoder(T)(T delegate() fn) {
  static if (is(T == float) || is(T == double) || is(T == float)) "%.16f".writefln(fn());
  else static if (is(T == void)) fn();
  else static if (is(T == string)) fn().writeln;
  else static if (isInputRange!T) {
    static if (!is(string == ElementType!T) && isInputRange!(ElementType!T)) foreach(r; fn()) r.toAnswerString.writeln;
    else foreach(r; fn()) r.writeln;
  }
  else fn().writeln;
}
void runSolver() {
  problem();
}
enum YESNO = [true: "Yes", false: "No"];

// -----------------------------------------------

auto asTuples(int L, T)(T matrix) {
  static if (__traits(compiles, L)) {
    return matrix.map!(row => mixin(format("tuple(%-(row[%s],%)])", L.iota)));
  } else {
    return matrix.map!(row => tuple());
  }
}