#1162637 (Java) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: EvbCFfp1XB
• 提出日時: 2026-05-02 20:55:19
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 1,934 ms / 2,000 ms
• コード長: 11,707 bytes
• コンパイル時間: 3,216 ms
• コンパイル使用メモリ: 92,120 KB
• 実行使用メモリ: 60,716 KB
• スコア: 2,213,733
• 最終ジャッジ日時: 2026-05-02 20:57:02
• 合計ジャッジ時間: 100,480 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    private static final double timeLimitSecond = 1.8;
    private static final int[] dr = { -1, 0, 0, 1, };
    private static final int[] dc = { 0, -1, 1, 0, };

    private static int N;
    private static int T;
    private static int[][] A;

    private static PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());
    private static Watch2 watch;

    private static ArrayList<Point> solution = new ArrayList<>();
    private static ArrayList<Point> bestSolution = new ArrayList<>();
    private static boolean[][] used;

    public static void main(String[] args) {
        try {
            read();
            solve();
            write();
            Utils.debug("time", watch.toString());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void read() {
        try (Scanner in = new Scanner(System.in)) {
            N = in.nextInt();
            watch = new Watch2();
            T = in.nextInt();
            System.err.println("[DATA] N = " + N);
            System.err.println("[DATA] T = " + T);
            System.err.flush();
            A = new int[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    A[r][c] = in.nextInt();
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private static void write() {
        StringBuilder sb = new StringBuilder();
        sb.append(bestSolution.size()).append("\n");
        for (Point p : bestSolution) {
            sb.append(p.r).append(" ").append(p.c).append("\n");
        }
        System.out.println(sb.toString().trim());
        System.out.flush();
    }

    private static void solve() {
        used = new boolean[N][N];
        solution.add(new Point(N / 2, N / 2));
        used[N / 2][N / 2] = true;
        solution.add(new Point(N / 2 - 1, N / 2));
        used[N / 2 - 1][N / 2] = true;
        score = calculateScore(solution);
        bestScore = score;
        sa();
    }

    private static double calculateScore(ArrayList<Point> solution) {
        if (solution.size() > T) {
            return -1e9;
        }
        boolean[][] used = new boolean[N][N];
        int sum = 0;
        for (int i = 0; i < solution.size(); i++) {
            Point p = solution.get(i);
            if (i > 0) {
                Point p2 = solution.get(i - 1);
                if (Math.abs(p.r - p2.r) + Math.abs(p.c - p2.c) != 1) {
                    return -1e9;
                }
            }
            if (used[p.r][p.c]) {
                return -1e9;
            }
            used[p.r][p.c] = true;
            sum += A[p.r][p.c];
        }
        return sum;
    }

    private static double temperature;
    private static double score;
    private static double bestScore;
    private static int[] countAC = new int[11];

    private static void sa() {
        final double startTemperature = 1000;
        final double endTemperature = 1e-9;
        final double startTimeSA = watch.elapsedSecond();
        temperature = startTemperature;
        long iters = 0;
        double deltaThresholdRatio = 0.05 - 1e-9;
        double thresholdRatio = deltaThresholdRatio;
        while (true) {
            iters++;
            if ((iters & ((1 << 5) - 1)) == 0) {
                final double tRatio = (watch.elapsedSecond() - startTimeSA) / (timeLimitSecond - startTimeSA);
                temperature = startTemperature + (endTemperature - startTemperature) * tRatio;
                if (tRatio > thresholdRatio) {
                    thresholdRatio += deltaThresholdRatio;
                    Utils.debug("iters", iters, "score", score, "best", bestScore, "T", temperature, "time", watch.elapsedSecond(), "countAC", countAC);
                }
                if (tRatio >= 1) {
                    break;
                }
            }
            removeAndAdd();
        }
    }

    private static void removeAndAdd() {
        if (rng.nextInt(2) == 0) {
            Collections.reverse(solution);
        }
        if (solution.isEmpty()) {
            Point p = new Point(rng.nextInt(N), rng.nextInt(N));
            used[p.r][p.c] = true;
            solution.add(p);
        }
        int index = rng.nextInt(Math.max(1, solution.size() - 5 - rng.nextInt(5)));

        ArrayList<Point> removes = new ArrayList<>();
        Point last = null;
        int length = 2 + rng.nextInt(5) + rng.nextInt(5);

        for (int i = 0; i < length; i++) {
            if (index >= solution.size()) {
                last = null;
                break;
            }
            Point remove = solution.remove(index);

            used[remove.r][remove.c] = false;

            removes.add(remove);
            last = remove;
        }
        int length2 = Math.min(T - solution.size() - 1, length + rng.nextInt(5));
        ArrayList<Point> path = dfs(length2, removes.get(0), last, removes);
        if (path.isEmpty()) {
            for (int i = 0; i < removes.size(); i++) {
                Point remove = removes.get(i);
                solution.add(index + i, remove);
                used[remove.r][remove.c] = true;
            }
            return;
        }
        for (int i = 0; i < path.size(); i++) {
            Point p = path.get(i);
            solution.add(index + i, p);
            used[p.r][p.c] = true;
        }
        double deltaScore = calculateScore(solution) - score;
        if (accept(deltaScore)) {
            score += deltaScore;
            countAC[0]++;
            if (score > bestScore) {
                bestScore = score;
                bestSolution.clear();
                for (Point p : solution) {
                    bestSolution.add(p);
                }
            }
        } else {
            for (int i = 0; i < path.size(); i++) {
                Point remove = solution.remove(index);
                used[remove.r][remove.c] = false;
            }
            for (int i = 0; i < removes.size(); i++) {
                Point remove = removes.get(i);
                solution.add(index + i, remove);
                used[remove.r][remove.c] = true;
            }
        }
    }

    private static int bestScoreDfs;
    private static ArrayList<Point> bestScoreDfsSolution = new ArrayList<>();

    private static ArrayList<Point> dfs(int length, Point point, Point point2, ArrayList<Point> current) {
        bestScoreDfs = 0;
        bestScoreDfsSolution.clear();
        ArrayList<Point> ps = new ArrayList<>();
        ps.add(point);
        used[point.r][point.c] = true;
        dfs(ps, 0, length, point, point2, 0, current);
        ps.remove(ps.size() - 1);
        used[point.r][point.c] = false;
        return bestScoreDfsSolution;
    }

    private static void dfs(ArrayList<Point> ps, int i, int length, Point point, Point point2, int scoreDfs, ArrayList<Point> current) {
        if (i >= length) {
            return;
        }
        Point p3 = ps.get(ps.size() - 1);
        if (point2 != null) {
            if (i + Math.abs(p3.r - point2.r) + Math.abs(p3.c - point2.c) >= length) {
                return;
            }
        }
        if (point2 == null || p3.equals(point2)) {
            if (!equals(ps, current)) {
                if (scoreDfs > bestScoreDfs) {
                    bestScoreDfs = scoreDfs;
                    bestScoreDfsSolution.clear();
                    for (Point p : ps) {
                        bestScoreDfsSolution.add(p);
                    }
                }
            }
            if (p3.equals(point2)) {
                return;
            }
        }

        for (int d = 0; d < dr.length; d++) {
            int nr = ps.get(i).r + dr[d];
            int nc = ps.get(i).c + dc[d];
            if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                continue;
            }
            if (used[nr][nc]) {
                continue;
            }
            used[nr][nc] = true;
            ps.add(new Point(nr, nc));
            dfs(ps, i + 1, length, point, point2, scoreDfs + A[nr][nc], current);
            ps.remove(ps.size() - 1);
            used[nr][nc] = false;
        }
    }

    private static boolean equals(ArrayList<Point> l, ArrayList<Point> l2) {
        if (l.size() != l2.size()) {
            return false;
        }
        for (int i = 0; i < l.size(); i++) {
            if (!l.get(i).equals(l2.get(i))) {
                return false;
            }
        }
        return true;
    }

    private static boolean accept(double delta) {
        if (delta >= 0) {
            return true;
        }
        double deltaPerTemperature = delta / temperature;
        if (deltaPerTemperature < -10.0) {
            return false;
        }
        return rng.nextDouble() < Math.exp(deltaPerTemperature);
    }
}

class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
        System.err.flush();
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

    public static boolean isValid(int v, int min, int minUpper) {
        return v >= min && v < minUpper;
    }
}

class PCG_XSH_RR {
    private long state = 5342;

    public PCG_XSH_RR(final long state) {
        this.state = state;
    }

    public int nextInt() {
        final long oldstate = state;
        state = oldstate * 6364136223846793005L + 521L;
        final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);
        final int rotation = (int) (oldstate >>> 59);
        return (xorshift >>> rotation) | (xorshift << (-rotation & 31));
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

    public int nextInt2(int n) {
        final int k = 16;
        final int x = (nextInt() & ((1 << k) - 1));
        return (x * n) >>> k;
    }

    public double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }
}

class Watch2 {
    private final long start;

    public Watch2() {
        start = System.nanoTime();
    }

    public double elapsedSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    @Override
    public String toString() {
        final long elapsedSecond = (long) (1e3 * elapsedSecond());
        return formatElapsedTimeWithUnits(elapsedSecond);
    }

    public static String formatElapsedTimeWithUnits(final long elapsedMillis) {
        final Duration duration = Duration.ofMillis(elapsedMillis);
        final long hours = duration.toHours();
        final long minutes = duration.toMinutesPart();
        final long seconds = duration.toSecondsPart();
        final long millis = duration.toMillisPart();
        final StringBuilder sb = new StringBuilder();
        if (hours > 0) {
            sb.append(hours).append("h");
        }
        if (minutes > 0 || hours > 0) {
            sb.append(minutes).append("m");
        }
        sb.append(seconds);
        if (minutes > 0 || hours > 0) {
        } else {
            sb.append(".").append(String.format("%03d", millis));
        }
        sb.append("s");
        return sb.toString().trim();
    }
}

class Point {
    int r;
    int c;

    public Point(int r, int c) {
        this.r = r;
        this.c = c;
    }

    public boolean equals(Point obj) {
        if (obj == null)
            return false;
        return c == obj.c && r == obj.r;
    }

    @Override
    public String toString() {
        return "(" + r + "," + c + ")";
    }
}