#1195069 (Java) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: 37zigen
• 提出日時: 2026-10-24 16:37:21
• 言語: Java (openjdk 27 + ACL)
• 結果: AC
• 実行時間: 1,879 ms / 2,000 ms
• コード長: 7,061 bytes
• コンパイル時間: 2,135 ms
• コンパイル使用メモリ: 96,928 KB
• 実行使用メモリ: 51,764 KB
• スコア: 164,018,331
• 最終ジャッジ日時: 2026-10-24 16:40:25
• 合計ジャッジ時間: 154,471 ms
• ジャッジサーバーID （参考情報）: judge4_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 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 starts uniformly from one of the N top-edge cells or N left-edge cells.
    // Top-edge starts move down; left-edge starts move right.
    static void generatePath(int[] path) {
        int start = random.nextInt(2 * n);
        if (start < n) {
            int col = start;
            path[0] = col; // (0, col)
            for (int row = 1; row < n; row++) {
                int low = Math.max(-1, -col);
                int high = Math.min(1, n - 1 - col);
                col += low + random.nextInt(high - low + 1);
                path[row] = row * n + col;
            }
        } else {
            int row = start - n;
            path[0] = row * n; // (row, 0)
            for (int col = 1; col < n; col++) {
                int low = Math.max(-1, -row);
                int high = Math.min(1, n - 1 - row);
                row += low + random.nextInt(high - low + 1);
                path[col] = row * n + col;
            }
        }
    }

    // Returns the sum of the squared dry-component sizes over the 10 shared samples.
    // The common factor 1 / (SAMPLE_COUNT * N * N) is omitted for candidate 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;
    }

    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();

        int[] path1 = new int[n];
        int[] path2 = 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 = 0;
        long bestValue = Long.MAX_VALUE;

        // Always evaluate the candidate that cuts both diagonals once.
        int diagonalStamp = ++cutStamp;
        for (int i = 0; i < n; i++) {
            cutMark[i * n + i] = diagonalStamp;
            cutMark[i * n + (n - 1 - i)] = diagonalStamp;
        }
        int diagonalCutCount = 0;
        for (int v = 0; v < cells; v++) {
            if (d[v] > 0 && cutMark[v] == diagonalStamp) diagonalCutCount++;
        }
        if (diagonalCutCount <= k) {
            bestValue = evaluate(diagonalStamp, cutMark, seen, queue, visitStamp);
            for (int v = 0; v < cells; v++) {
                bestCut[v] = d[v] > 0 && cutMark[v] == diagonalStamp;
            }
        }

        // Leave a small safety margin before the 2-second contest limit.
        long deadline = startTime + TIME_LIMIT_NS;
        while (System.nanoTime() < deadline) {
            generatePath(path1);
            generatePath(path2);
            int stamp = ++cutStamp;
            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++;
            }
            if (cutCount > k) continue;

            long value = evaluate(stamp, cutMark, seen, queue, visitStamp);
            if (value < bestValue) {
                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);
    }
}