結果
| 問題 | No.5025 Forest Fire |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2026-10-24 17:07:55 |
| 言語 | Java (openjdk 27 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,949 ms / 2,000 ms |
| + 820µs | |
| コード長 | 12,726 bytes |
| 記録 | |
| コンパイル時間 | 2,119 ms |
| コンパイル使用メモリ | 96,360 KB |
| 実行使用メモリ | 57,872 KB |
| スコア | 175,287,075 |
| 最終ジャッジ日時 | 2026-10-24 17:10:42 |
| 合計ジャッジ時間 | 161,544 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / <nil> |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 50 |
ソースコード
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Random;
public class Main {
static final int SAMPLE_COUNT = 10;
static final int MAX_SEGMENT_LENGTH = 20;
static final long TIME_LIMIT_NS = 1_850_000_000L;
static int n, k, cells;
static int[] d;
static boolean[][] dry;
static final Random random = new Random();
static final class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
String next() throws IOException {
StringBuilder sb = new StringBuilder();
int c;
do {
c = in.read();
} while (c <= ' ' && c != -1);
while (c > ' ') {
sb.append((char) c);
c = in.read();
}
return sb.toString();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
static void generateDrySamples() {
dry = new boolean[SAMPLE_COUNT][cells];
for (int s = 0; s < SAMPLE_COUNT; s++) {
for (int v = 0; v < cells; v++) {
dry[s][v] = random.nextInt(10) < d[v];
}
}
}
// A path is indexed by its forward coordinate: column for a horizontal
// path and row for a vertical path. The other coordinate may change by
// -1, 0, or +1 at each step.
static int transverse(int vertex, boolean horizontal) {
return horizontal ? vertex / n : vertex % n;
}
static int vertexAt(int index, int transverse, boolean horizontal) {
return horizontal ? transverse * n + index : index * n + transverse;
}
// Randomized DFS for the interval [left, right]. The start vertex stays
// fixed. If right is not the last index, the destination must match the
// old path vertex exactly; at the terminal board edge, the destination is
// free. The distance bound prunes states that cannot reach a fixed target.
static boolean dfsSegment(int[] path, boolean horizontal, int index, int right,
int coordinate, int target, boolean fixedTarget) {
path[index] = vertexAt(index, coordinate, horizontal);
if (index == right) {
return !fixedTarget || coordinate == target;
}
int nextIndex = index + 1;
int low = Math.max(0, coordinate - 1);
int high = Math.min(n - 1, coordinate + 1);
int[] choices = new int[high - low + 1];
int count = 0;
for (int value = low; value <= high; value++) choices[count++] = value;
for (int i = count - 1; i > 0; i--) {
int j = random.nextInt(i + 1);
int temp = choices[i];
choices[i] = choices[j];
choices[j] = temp;
}
for (int nextCoordinate : choices) {
// For a left-to-right path, |vertical difference| cannot exceed
// the remaining horizontal distance. The vertical case is symmetric.
if (fixedTarget && Math.abs(target - nextCoordinate) > right - nextIndex) {
continue;
}
if (dfsSegment(path, horizontal, nextIndex, right, nextCoordinate,
target, fixedTarget)) {
return true;
}
}
return false;
}
static void rerandomizeSegment(int[] path, boolean horizontal, int left, int right) {
if (left >= right) return;
int startCoordinate = transverse(path[left], horizontal);
boolean fixedTarget = right < n - 1;
int target = transverse(path[right], horizontal);
// When the destination is internal it is fixed exactly. When it is
// on the far edge, any coordinate on that edge is accepted.
if (!dfsSegment(path, horizontal, left, right, startCoordinate, target, fixedTarget)) {
// The old segment always provides a feasible path, so this is only
// a defensive fallback if the DFS implementation is changed later.
return;
}
}
// Reverse-direction DFS: start at the tail-side vertex and move toward
// index 0. The index-0 endpoint is free; otherwise the left endpoint must
// connect exactly to the unchanged part of the path.
static boolean dfsSegmentReverse(int[] path, boolean horizontal, int index, int left,
int coordinate, int target, boolean fixedTarget) {
path[index] = vertexAt(index, coordinate, horizontal);
if (index == left) {
return !fixedTarget || coordinate == target;
}
int nextIndex = index - 1;
int low = Math.max(0, coordinate - 1);
int high = Math.min(n - 1, coordinate + 1);
int[] choices = new int[high - low + 1];
int count = 0;
for (int value = low; value <= high; value++) choices[count++] = value;
for (int i = count - 1; i > 0; i--) {
int j = random.nextInt(i + 1);
int temp = choices[i];
choices[i] = choices[j];
choices[j] = temp;
}
for (int nextCoordinate : choices) {
// Remaining steps are nextIndex - left, in reverse direction.
if (fixedTarget && Math.abs(target - nextCoordinate) > nextIndex - left) {
continue;
}
if (dfsSegmentReverse(path, horizontal, nextIndex, left, nextCoordinate,
target, fixedTarget)) {
return true;
}
}
return false;
}
static void rerandomizeSegmentReverse(int[] path, boolean horizontal, int left, int right) {
if (left >= right) return;
int startCoordinate = transverse(path[right], horizontal);
boolean fixedTarget = left > 0;
int target = transverse(path[left], horizontal);
if (!dfsSegmentReverse(path, horizontal, right, left, startCoordinate,
target, fixedTarget)) {
// The old segment is always a feasible fallback.
return;
}
}
// Sum of squared dry-component sizes over the 10 shared samples.
// The common factor 1 / (SAMPLE_COUNT * N * N) is omitted for comparison.
static long evaluate(int cutStamp, int[] cutMark, int[] seen, int[] queue,
int[] visitStamp) {
long total = 0;
for (int s = 0; s < SAMPLE_COUNT; s++) {
int mark = ++visitStamp[0];
for (int v = 0; v < cells; v++) {
if (!dry[s][v] || cutMark[v] == cutStamp || seen[v] == mark) continue;
int head = 0;
int tail = 0;
queue[tail++] = v;
seen[v] = mark;
while (head < tail) {
int u = queue[head++];
int row = u / n;
int col = u - row * n;
int w;
if (row > 0) {
w = u - n;
if (dry[s][w] && cutMark[w] != cutStamp && seen[w] != mark) {
seen[w] = mark;
queue[tail++] = w;
}
}
if (row + 1 < n) {
w = u + n;
if (dry[s][w] && cutMark[w] != cutStamp && seen[w] != mark) {
seen[w] = mark;
queue[tail++] = w;
}
}
if (col > 0) {
w = u - 1;
if (dry[s][w] && cutMark[w] != cutStamp && seen[w] != mark) {
seen[w] = mark;
queue[tail++] = w;
}
}
if (col + 1 < n) {
w = u + 1;
if (dry[s][w] && cutMark[w] != cutStamp && seen[w] != mark) {
seen[w] = mark;
queue[tail++] = w;
}
}
}
total += (long) tail * tail;
}
}
return total;
}
static int markCuts(int[] path1, int[] path2, int stamp, int[] cutMark) {
for (int v : path1) cutMark[v] = stamp;
for (int v : path2) cutMark[v] = stamp;
int cutCount = 0;
for (int v = 0; v < cells; v++) {
if (d[v] > 0 && cutMark[v] == stamp) cutCount++;
}
return cutCount;
}
public static void main(String[] args) throws IOException {
long startTime = System.nanoTime();
FastScanner fs = new FastScanner();
n = fs.nextInt();
k = fs.nextInt();
cells = n * n;
d = new int[cells];
for (int r = 0; r < n; r++) {
String row = fs.next();
for (int c = 0; c < n; c++) {
d[r * n + c] = row.charAt(c) - '0';
}
}
generateDrySamples();
// Initial solution: a plus-shaped cross through the center row/column.
int[] path1 = new int[n]; // horizontal path
int[] path2 = new int[n]; // vertical path
int middle = n / 2;
for (int i = 0; i < n; i++) {
path1[i] = middle * n + i;
path2[i] = i * n + middle;
}
int[] candidate1 = new int[n];
int[] candidate2 = new int[n];
int[] cutMark = new int[cells];
int[] seen = new int[cells];
int[] queue = new int[cells];
int[] visitStamp = {0};
boolean[] bestCut = new boolean[cells];
int cutStamp = 1;
int initialCutCount = markCuts(path1, path2, cutStamp, cutMark);
long currentValue = evaluate(cutStamp, cutMark, seen, queue, visitStamp);
long bestValue = currentValue;
for (int v = 0; v < cells; v++) {
bestCut[v] = d[v] > 0 && cutMark[v] == cutStamp;
}
long deadline = startTime + TIME_LIMIT_NS;
long trials = 0, withinK = 0, evaluated = 1, improvements = 0;
int maxLength = Math.min(MAX_SEGMENT_LENGTH, n - 1);
// Hill climbing: mutate one random segment of one of the two paths.
while (maxLength >= 2 && System.nanoTime() < deadline) {
trials++;
System.arraycopy(path1, 0, candidate1, 0, n);
System.arraycopy(path2, 0, candidate2, 0, n);
int anchor = random.nextInt(n); // randomly selected path vertex
int length = 1 + random.nextInt(maxLength); // at most 20 steps
boolean horizontal = random.nextBoolean();
boolean reverse = random.nextBoolean();
int left, right;
if (!reverse) {
left = anchor;
right = Math.min(n - 1, left + length); // clamp at the tail-side end
} else {
right = anchor;
left = Math.max(0, right - length); // clamp at the head-side end
}
int[] candidatePath = horizontal ? candidate1 : candidate2;
if (reverse) {
rerandomizeSegmentReverse(candidatePath, horizontal, left, right);
} else {
rerandomizeSegment(candidatePath, horizontal, left, right);
}
int stamp = ++cutStamp;
int cutCount = markCuts(candidate1, candidate2, stamp, cutMark);
if (cutCount > k) continue;
withinK++;
long value = evaluate(stamp, cutMark, seen, queue, visitStamp);
evaluated++;
if (value < currentValue) {
improvements++;
currentValue = value;
System.arraycopy(candidate1, 0, path1, 0, n);
System.arraycopy(candidate2, 0, path2, 0, n);
bestValue = value;
for (int v = 0; v < cells; v++) {
bestCut[v] = d[v] > 0 && cutMark[v] == stamp;
}
}
}
int answerCount = 0;
for (boolean cut : bestCut) if (cut) answerCount++;
StringBuilder out = new StringBuilder();
out.append(answerCount).append('\n');
for (int v = 0; v < cells; v++) {
if (bestCut[v]) out.append(v / n).append(' ').append(v % n).append('\n');
}
System.out.print(out);
System.err.printf("initialCutCount=%d trials=%d withinK=%d evaluated=%d improvements=%d bestValue=%d elapsed=%.3fms%n",
initialCutCount, trials, withinK, evaluated, improvements, bestValue,
(System.nanoTime() - startTime) / 1e6);
}
}