#929674 (Java21) No.5019 Hakai Project

提出ソース
結果

問題	No.5019 Hakai Project
ユーザー	EvbCFfp1XB
提出日時	2023-11-19 18:47:09
言語	Java21 (openjdk 21)
結果	AC
実行時間	2,990 ms / 3,000 ms
コード長	22,447 bytes
コンパイル時間	3,076 ms
コンパイル使用メモリ	92,740 KB
実行使用メモリ	66,960 KB
スコア	1,895,056,586
最終ジャッジ日時	2023-11-19 18:49:47
合計ジャッジ時間	157,380 ms
ジャッジサーバーID （参考情報）	judge11 / judge15
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,889 ms 65,204 KB
testcase_01	AC	2,903 ms 66,824 KB
testcase_02	AC	2,889 ms 64,592 KB
testcase_03	AC	2,889 ms 64,588 KB
testcase_04	AC	2,902 ms 65,096 KB
testcase_05	AC	2,887 ms 64,564 KB
testcase_06	AC	2,900 ms 65,152 KB
testcase_07	AC	2,907 ms 66,812 KB
testcase_08	AC	2,934 ms 66,860 KB
testcase_09	AC	2,901 ms 65,164 KB
testcase_10	AC	2,892 ms 66,960 KB
testcase_11	AC	2,906 ms 66,796 KB
testcase_12	AC	2,896 ms 64,680 KB
testcase_13	AC	2,898 ms 62,844 KB
testcase_14	AC	2,902 ms 66,404 KB
testcase_15	AC	2,905 ms 66,716 KB
testcase_16	AC	2,898 ms 65,364 KB
testcase_17	AC	2,898 ms 65,340 KB
testcase_18	AC	2,895 ms 66,728 KB
testcase_19	AC	2,905 ms 66,920 KB
testcase_20	AC	2,926 ms 65,148 KB
testcase_21	AC	2,906 ms 65,416 KB
testcase_22	AC	2,929 ms 65,560 KB
testcase_23	AC	2,889 ms 65,216 KB
testcase_24	AC	2,897 ms 65,324 KB
testcase_25	AC	2,908 ms 65,464 KB
testcase_26	AC	2,908 ms 64,648 KB
testcase_27	AC	2,889 ms 66,880 KB
testcase_28	AC	2,909 ms 65,268 KB
testcase_29	AC	2,903 ms 66,888 KB
testcase_30	AC	2,895 ms 66,564 KB
testcase_31	AC	2,899 ms 65,244 KB
testcase_32	AC	2,891 ms 64,760 KB
testcase_33	AC	2,916 ms 64,680 KB
testcase_34	AC	2,889 ms 62,720 KB
testcase_35	AC	2,904 ms 65,444 KB
testcase_36	AC	2,923 ms 66,784 KB
testcase_37	AC	2,902 ms 65,068 KB
testcase_38	AC	2,901 ms 66,848 KB
testcase_39	AC	2,901 ms 65,256 KB
testcase_40	AC	2,888 ms 66,728 KB
testcase_41	AC	2,926 ms 65,380 KB
testcase_42	AC	2,922 ms 65,320 KB
testcase_43	AC	2,901 ms 65,332 KB
testcase_44	AC	2,902 ms 66,756 KB
testcase_45	AC	2,926 ms 65,416 KB
testcase_46	AC	2,884 ms 65,336 KB
testcase_47	AC	2,886 ms 64,544 KB
testcase_48	AC	2,990 ms 66,704 KB
testcase_49	AC	2,901 ms 65,084 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    private static final int EMPTY = 0;
    private static final int BUILDING = 1;
    private static final int SHOP = 2;
    private static final int margin = 9;
    private static final int shift = 0;
    private int N;
    private int M;
    private int[][] map;
    private int[] cost;
    private int[][] dy;
    private int[][] dx;
    static Watch watch = new Watch();
    static PCG_XSH_RR rng = new PCG_XSH_RR(114514L);
    private SAState sa = new SAState();
    private int score;
    private int[][] cover;
    private ArrayList<BombPoint>[] points = new ArrayList[4];
    private Region[] regions;
    private ArrayList<BombPoint>[] shops = new ArrayList[4];

    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private void run() {
        read();
        regions = new Region[] { new Region(0, N / 2, 0, N / 2, 0 + margin - shift, N / 2 - margin - shift, 0 + margin - shift, N / 2 - margin - shift), new Region(0, N / 2, N / 2, N, 0 + margin - shift, N / 2 - margin - shift, N / 2 + margin + shift, N - margin + shift), new Region(N / 2, N, N / 2, N, N / 2 + margin + shift, N - margin + shift, N / 2 + margin + shift, N - margin + shift), new Region(N / 2, N, 0, N / 2, N / 2 + margin + shift, N - margin + shift, 0 + margin - shift, N / 2 - margin - shift), };
        for (int i = 0; i < points.length; i++) {
            points[i] = new ArrayList<>();
        }
        for (int i = 0; i < shops.length; i++) {
            shops[i] = new ArrayList<>();
        }
        for (int regioni = 0; regioni < points.length; regioni++) {
            Region region = regions[regioni];
            for (int r = region.minR; r < region.maxR; r++) {
                for (int c = region.minC; c < region.maxC; c++) {
                    if (map[r][c] == SHOP) {
                        shops[regioni].add(new BombPoint(r, c, -1));
                    }
                }
            }
        }
        for (int regioni = 0; regioni < points.length; regioni++) {
            Utils.debug("regioni", regioni);
            Region region = regions[regioni];
            Point nearestShop = null;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (cover[r][c] == 0 && map[r][c] == SHOP) {
                        if (nearestShop == null || euclideanDistance(r, c, (region.minR2 + region.maxR2) / 2, (region.minC2 + region.maxC2) / 2) < euclideanDistance(nearestShop.r, nearestShop.c, (region.minR2 + region.maxR2) / 2, (region.minC2 + region.maxC2) / 2)) {
                            nearestShop = new Point(r, c);
                        }
                    }
                }
            }
            points[regioni].add(new BombPoint(nearestShop.r, nearestShop.c, -1));
            setCoverGreedy(region, regioni);
        }
        score = calculateScore();
        Utils.debug("score", score);
        multiSA();
        ArrayList<Move> moves = new ArrayList<>();
        Point halc = new Point(0, 0);
        for (int i = 0; i < points.length; i++) {
            ArrayList<BombPoint> ps = points[i];
            for (int j = 0; j < ps.size(); j++) {
                BombPoint p = ps.get(j);
                if (j == 0) {
                    move(p.r, p.c, moves, halc);
                    for (int k = 1; k < ps.size(); k++) {
                        moves.add(new Move(2, "" + (1 + ps.get(k).bomb)));
                    }
                } else {
                    move(p.r, p.c, moves, halc);
                    moves.add(new Move(3, "" + (1 + p.bomb)));
                }
            }
        }
        System.out.println(moves.size());
        for (Move move : moves) {
            System.out.println(move.type + " " + move.s);
        }
        System.out.flush();
    }

    int[][] cover2;

    private int calculateScore() {
        if (cover2 == null) {
            cover2 = new int[N][N];
        }
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                cover2[r][c] = 0;
            }
        }
        int score = 0;
        int r = 0;
        int c = 0;
        for (int i = 0; i < points.length; i++) {
            ArrayList<BombPoint> ps = points[i];
            for (int j = 0; j < ps.size(); j++) {
                BombPoint p = ps.get(j);
                if (j == 0) {
                    score += 2 * manhattanDistance(r, c, p.r, p.c) * 1 * 1;
                    if (cover2[p.r][p.c] != 0) {
                        score += 1e9;
                    }
                    for (int k = 1; k < ps.size(); k++) {
                        score += cost[ps.get(k).bomb];
                    }
                } else {
                    score += 2 * manhattanDistance(r, c, p.r, p.c) * (1 + ps.size() - j) * (1 + ps.size() - j);
                    updateCover2(cover2, p.r, p.c, p.bomb, 1);
                }
                r = p.r;
                c = p.c;
            }
        }
        return score;
    }

    private static void move(int r, int c, ArrayList<Move> moves, Point halc) {
        while (halc.r != r) {
            if (halc.r < r) {
                moves.add(new Move(1, "D"));
                halc.r++;
            } else {
                moves.add(new Move(1, "U"));
                halc.r--;
            }
        }
        while (halc.c != c) {
            if (halc.c < c) {
                moves.add(new Move(1, "R"));
                halc.c++;
            } else {
                moves.add(new Move(1, "L"));
                halc.c--;
            }
        }
    }

    private static final int manhattanDistance(int r1, int c1, int r2, int c2) {
        int deltaR = r2 - r1;
        int deltaC = c2 - c1;
        return Math.abs(deltaR) + Math.abs(deltaC);
    }

    private static final double euclideanDistance(int r1, int c1, int r2, int c2) {
        int deltaR = r2 - r1;
        int deltaC = c2 - c1;
        return Math.sqrt(deltaR * deltaR + deltaC * deltaC);
    }

    private void setCoverGreedy(Region region, int index) {
        while (!isCoverd(cover, region)) {
            double max = 0;
            int maxBomb = -1;
            int maxR = -1;
            int maxC = -1;
            for (int r2 = region.minR2; r2 < region.maxR2; r2++) {
                for (int c2 = region.minC2; c2 < region.maxC2; c2++) {
                    for (int bomb = 0; bomb < M; bomb++) {
                        int count = 0;
                        for (int i = 0; i < dy[bomb].length; i++) {
                            int nr = r2 + dy[bomb][i];
                            int nc = c2 + dx[bomb][i];
                            if (!Utils.isValid(nr, region.minR, region.maxR) || !Utils.isValid(nc, region.minC, region.maxC)) {
                                continue;
                            }
                            if (cover[nr][nc] != 0) {
                                continue;
                            }
                            count++;
                        }
                        if (count > max) {
                            max = count;
                            maxBomb = bomb;
                            maxR = r2;
                            maxC = c2;
                        }
                    }
                }
            }
            points[index].add(new BombPoint(maxR, maxC, maxBomb));
            updateCover(maxR, maxC, maxBomb, 1);
        }
    }

    private void setCoverGreedy2(int index0) {
        Region region = regions[index0];
        while (!isCoverd(cover)) {
            double max = 0;
            int maxBomb = -1;
            int maxR = -1;
            int maxC = -1;
            int r2 = (int) (region.minR2 + (region.maxR2 - region.minR2) * rng.nextDouble());
            {
                int c2 = (int) (region.minC2 + (region.maxC2 - region.minC2) * rng.nextDouble());
                {
                    int bomb = rng.nextInt(M);
                    {
                        int count = 0;
                        for (int i = 0; i < dy[bomb].length; i++) {
                            int nr = r2 + dy[bomb][i];
                            int nc = c2 + dx[bomb][i];
                            if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                                continue;
                            }
                            if (cover[nr][nc] != 0) {
                                continue;
                            }
                            count++;
                        }
                        if (count > max) {
                            max = count;
                            maxBomb = bomb;
                            maxR = r2;
                            maxC = c2;
                        }
                    }
                }
            }
            if (maxBomb == -1) {
                continue;
            }
            points[index0].add(new BombPoint(maxR, maxC, maxBomb));
            updateCover(maxR, maxC, maxBomb, 1);
        }
    }

    private void updateCover(int r, int c, int bomb, int value) {
        if (bomb < 0) {
            return;
        }
        for (int i = 0; i < dy[bomb].length; i++) {
            int nr = r + dy[bomb][i];
            int nc = c + dx[bomb][i];
            if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                continue;
            }
            cover[nr][nc] += value;
        }
    }

    private void updateCover2(int[][] cover, int r, int c, int bomb, int value) {
        if (bomb < 0) {
            return;
        }
        for (int i = 0; i < dy[bomb].length; i++) {
            int nr = r + dy[bomb][i];
            int nc = c + dx[bomb][i];
            if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {
                continue;
            }
            cover[nr][nc] += value;
        }
    }

    private void multiSA() {
        int numRestart = 1;
        double startTime = watch.getSecond();
        double endTime = 2.7;
        double remainTime = endTime - startTime;
        double startStartTemperature = 1e2;
        double endStartTemperature = 1e-9;
        for (double restart = 0; restart < numRestart; restart++) {
            sa.startTime = startTime + remainTime * restart / numRestart;
            sa.endTime = startTime + remainTime * (restart + 1) / numRestart;
            sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);
            sa.endTemperature = 1e-9;
            SA();
        }
        Utils.debug("multiSA", "score", score, "time", watch.getSecondString());
    }

    private void SA() {
        final double deltaSecond = (sa.endTime - sa.startTime) * 0.999 / 10;
        double thresholdSecond = sa.startTime + deltaSecond;
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 3) - 1)) == 0) {
                sa.update();
                if (sa.time > thresholdSecond) {
                    thresholdSecond += deltaSecond;
                    Utils.debug(sa.numIterations, String.format("%6.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%6.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%5d", score), String.format("%8.6f", 1.0 / sa.inverseTemperature), String.format("%8.6f", 1.0 / sa.lastAcceptTemperature), sa.time);
                }
                if (sa.isTLE()) {
                    break;
                }
            }
            mutate();
        }
    }

    private void mutate() {
        double random = 3 * rng.nextDouble();
        if (random < 1) {
            swap();
        } else if (random < 2) {
            add();
        } else if (random < 3) {
            shop();
        }
    }

    private void add() {
        int index = rng.nextInt(points.length);
        ArrayList<BombPoint> ps = points[index];
        ArrayList<BombPoint> copy = new ArrayList<>();
        for (int i = 0; i < ps.size(); i++) {
            copy.add(ps.get(i));
        }
        int random = 1 + rng.nextInt(2);
        for (int i = 0; i < random; i++) {
            if (ps.size() <= 1) {
                continue;
            }
            int index2 = 1 + rng.nextInt(ps.size() - 1);
            BombPoint removed = ps.remove(index2);
            updateCover(removed.r, removed.c, removed.bomb, -1);
        }
        setCoverGreedy2(index);
        int deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
        } else {
            for (int i = ps.size() - 1; i >= 0; i--) {
                BombPoint removed = ps.remove(i);
                updateCover(removed.r, removed.c, removed.bomb, -1);
            }
            for (int i = 0; i < copy.size(); i++) {
                BombPoint bombPoint = copy.get(i);
                ps.add(bombPoint);
                updateCover(bombPoint.r, bombPoint.c, bombPoint.bomb, 1);
            }
        }
    }

    private void swap() {
        int index = rng.nextInt(points.length);
        if (points[index].size() <= 2) {
            return;
        }
        int index1 = 1 + rng.nextInt(points[index].size() - 1);
        int index2 = 1 + rng.nextInt(points[index].size() - 1);
        if (index1 == index2) {
            return;
        }
        Collections.swap(points[index], index1, index2);
        int deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
        } else {
            Collections.swap(points[index], index1, index2);
        }
    }

    private void shop() {
        int index = rng.nextInt(points.length);
        BombPoint current = points[index].get(0);
        BombPoint shop = shops[index].get(rng.nextInt(shops[index].size()));
        points[index].set(0, shop);
        int deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
        } else {
            points[index].set(0, current);
        }
    }

    private static boolean isCoverd(int[][] cover2, Region region) {
        return isCoverd(cover2, region.minR, region.maxR, region.minC, region.maxC);
    }

    private boolean isCoverd(int[][] cover2) {
        return isCoverd(cover2, 0, N, 0, N);
    }

    private static boolean isCoverd(int[][] cover2, int minR, int maxR, int minC, int maxC) {
        for (int r = minR; r < maxR; r++) {
            for (int c = minC; c < maxC; c++) {
                if (cover2[r][c] <= 0) {
                    return false;
                }
            }
        }
        return true;
    }

    private void read() {
        try (final Scanner in = new Scanner(System.in)) {
            N = in.nextInt();
            watch.init();
            M = in.nextInt();
            map = new int[N][N];
            for (int r = 0; r < N; r++) {
                String line = in.next();
                for (int c = 0; c < N; c++) {
                    char ch = line.charAt(c);
                    map[r][c] = ch == '.' ? EMPTY : ch == '#' ? BUILDING : SHOP;
                }
            }
            cost = new int[M];
            dy = new int[M][];
            dx = new int[M][];
            for (int i = 0; i < M; i++) {
                cost[i] = in.nextInt();
                int l = in.nextInt();
                int[] dy2 = new int[l];
                int[] dx2 = new int[l];
                for (int j = 0; j < l; j++) {
                    dy2[j] = in.nextInt();
                    dx2[j] = in.nextInt();
                }
                dy[i] = dy2;
                dx[i] = dx2;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        cover = new int[N][N];
    }
}

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 Watch {
    private long start;

    public Watch() {
        init();
    }

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

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }
}

final 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 double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }
}

class SAState {
    public static final boolean useTime = true;
    public double startTime;
    public double endTime;
    public double time;
    public double startTemperature;
    public double endTemperature;
    public double inverseTemperature;
    public double lastAcceptTemperature;
    public double startRange;
    public double endRange;
    public double range;
    public int numIterations;
    public int validIterations;
    public int acceptIterations;
    private double[] log = new double[32768];

    public SAState() {
        for (int i = 0; i < log.length; i++) {
            log[i] = Math.log((i + 0.5) / log.length);
        }
    }

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;
        startTime = useTime ? Main.watch.getSecond() : numIterations;
        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
    }

    public boolean useExp = !true;

    public void updateTemperature() {
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);
            inverseTemperature = 1.0 / temperature;
        } else {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double temperature = interpolate(startY, endY, time0to1);
            inverseTemperature = 1.0 / temperature;
        }
    }

    private double elapsedPercentage(double min, double max, double v) {
        return (v - min) / (max - min);
    }

    private double interpolate(double v0, double v1, double d0to1) {
        return v0 + (v1 - v0) * d0to1;
    }

    public void updateRange() {
        range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
    }

    public void updateTime() {
        time = useTime ? Main.watch.getSecond() : numIterations;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        return acceptS(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;
        if (deltaScore > -1e-9) {
            acceptIterations++;
            return true;
        }
        double d = deltaScore * inverseTemperature;
        if (d < -10) {
            return false;
        }
        if (log[Main.rng.nextInt() & 32767] < d) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

    public boolean acceptS(double deltaScore) {
        validIterations++;
        if (deltaScore < 1e-9) {
            acceptIterations++;
            return true;
        }
        double d = -deltaScore * inverseTemperature;
        if (d < -10) {
            return false;
        }
        if (log[Main.rng.nextInt() & 32767] < d) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }
}

class Point {
    int r;
    int c;

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

class BombPoint {
    int r;
    int c;
    int bomb;

    public BombPoint(int r, int c, int bomb) {
        super();
        this.r = r;
        this.c = c;
        this.bomb = bomb;
    }
}

class Move {
    int type;
    String s;

    public Move(int type, String s) {
        super();
        this.type = type;
        this.s = s;
    }
}

class Region {
    int minR;
    int maxR;
    int minC;
    int maxC;
    int minR2;
    int maxR2;
    int minC2;
    int maxC2;

    public Region(int minR, int maxR, int minC, int maxC, int minR2, int maxR2, int minC2, int maxC2) {
        super();
        this.minR = minR;
        this.maxR = maxR;
        this.minC = minC;
        this.maxC = maxC;
        this.minR2 = minR2;
        this.maxR2 = maxR2;
        this.minC2 = minC2;
        this.maxC2 = maxC2;
    }

    public Region(int minR, int maxR, int minC, int maxC) {
        super();
        this.minR = minR;
        this.maxR = maxR;
        this.minC = minC;
        this.maxC = maxC;
    }
}
yukicoder

結果

テストケース

ソースコード
