#783400 (Java21) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	EvbCFfp1XB
提出日時	2022-07-30 17:56:19
言語	Java21 (openjdk 21)
結果	AC
実行時間	948 ms / 1,000 ms
コード長	22,719 bytes
コンパイル時間	2,981 ms
実行使用メモリ	58,416 KB
スコア	8,837,448
最終ジャッジ日時	2022-07-30 17:56:53
合計ジャッジ時間	33,611 ms
ジャッジサーバーID （参考情報）	judge11 / judge14
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	905 ms 53,704 KB
testcase_01	AC	918 ms 56,136 KB
testcase_02	AC	940 ms 56,168 KB
testcase_03	AC	934 ms 56,068 KB
testcase_04	AC	922 ms 56,132 KB
testcase_05	AC	921 ms 50,400 KB
testcase_06	AC	905 ms 56,180 KB
testcase_07	AC	922 ms 56,020 KB
testcase_08	AC	906 ms 50,056 KB
testcase_09	AC	911 ms 56,236 KB
testcase_10	AC	948 ms 56,148 KB
testcase_11	AC	918 ms 56,212 KB
testcase_12	AC	921 ms 56,064 KB
testcase_13	AC	942 ms 56,256 KB
testcase_14	AC	906 ms 56,116 KB
testcase_15	AC	926 ms 50,416 KB
testcase_16	AC	915 ms 56,200 KB
testcase_17	AC	930 ms 56,128 KB
testcase_18	AC	926 ms 50,156 KB
testcase_19	AC	914 ms 56,160 KB
testcase_20	AC	909 ms 53,812 KB
testcase_21	AC	911 ms 50,280 KB
testcase_22	AC	914 ms 50,420 KB
testcase_23	AC	896 ms 53,588 KB
testcase_24	AC	940 ms 56,196 KB
testcase_25	AC	917 ms 53,616 KB
testcase_26	AC	928 ms 56,152 KB
testcase_27	AC	922 ms 56,180 KB
testcase_28	AC	939 ms 58,416 KB
testcase_29	AC	910 ms 56,380 KB
権限があれば一括ダウンロードができます
ソースコード

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

public class Main {
    private int N;
    private int M;
    private int[] r;
    private int[] c;

    private int[] r2;
    private int[] c2;
    private ArrayList<Integer> types;
    private ArrayList<Integer> indexes;
    private double score;

    private int[] bestR2;
    private int[] bestC2;
    private ArrayList<Integer> bestType;
    private ArrayList<Integer> bestIndex;
    private double bestScore;

    private static final double[] alpha = { 0, 0, 25, 5, 1, };

    public static SAState sa = new SAState();

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

    private void run() {
        read();
        greedy();
        multiSA();
        write();
    }

    private void write() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            sb.append(bestR2[i] + " " + bestC2[i]).append("\n");
        }

        final int V = bestType.size();
        sb.append(V + 1).append("\n");

        int index = 0;
        for (int i = 0; i < V; i++) {
            if (bestType.get(i) == 1 && bestIndex.get(i) == 0) {
                index = i;
            }
        }

        for (int i = 0; i < V; i++) {
            sb.append(bestType.get((index + i) % V) + " " + (bestIndex.get((index + i) % V) + 1)).append("\n");
        }
        sb.append(bestType.get((index + 0) % V) + " " + (bestIndex.get((index + 0) % V) + 1)).append("\n");

        System.out.print(sb.toString());
        System.out.flush();
    }

    private void greedy() {
        r2 = new int[M];
        c2 = new int[M];
        for (int i = 0; i < M; i++) {
            r2[i] = (int) (500 + 250 * Math.sin(Math.toRadians(i * 360.0 / M)));
            c2[i] = (int) (500 + 250 * Math.cos(Math.toRadians(i * 360.0 / M)));
        }
        bestR2 = new int[M];
        bestC2 = new int[M];
        types = new ArrayList<>();
        indexes = new ArrayList<>();
        bestType = new ArrayList<>();
        bestIndex = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            types.add(1);
            indexes.add(i);
            types.add(2);
            indexes.add(i * M / N);
        }
        score = calculateScore();
        bestScore = 1e99;
        saveBest();
    }

    private void read() {
        try (Scanner in = new Scanner(System.in)) {
            N = in.nextInt();
            Constants.watch.init();
            M = in.nextInt();
            r = new int[N];
            c = new int[N];
            IntStream.range(0, N).forEach(i -> {
                r[i] = in.nextInt();
                c[i] = in.nextInt();
            });
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private void multiSA() {
        int numRestart = 1;

        double startTime = Constants.watch.getSecond();
        double endTime = 1 - 0.25;
        double remainTime = endTime - startTime;

        double startStartTemperature = 50000;
        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.startRange = 200;
            sa.endRange = 10;
            SA();
        }
        Utils.debug("multiSA", "score", score2(score), "time", Constants.watch.getSecondString());
    }

    private double score2(double score) {
        return 1e9 / (1e3 + Math.sqrt(score));
    }

    private void SA() {
        double second = Constants.watch.getSecond();
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 5) - 1)) == 0) {
                sa.update();
                if (sa.time > second) {
                    second += 1;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%05.3f", score2(score)), String.format("%05.3f", score2(bestScore)), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }
                if (sa.isTLE()) {
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%05.3f", score2(score)), String.format("%05.3f", score2(bestScore)), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    break;
                }
            }

            mutate();
        }
    }

    private void mutate() {
        double random = 4.2 * Constants.RNG.nextDouble();
        if (random < 1) {
            reverse();
        } else if (random < 2) {
            swap();
        } else if (random < 3) {
            addISS();
        } else if (random < 4) {
            removeISS();
        } else if (random < 4.1) {
            addBestISS();
        } else if (random < 4.2) {
            moveISS();
        } else if (random < 7) {
            insert();
        }
    }

    private void reverse() {
        final int V = types.size();
        int i1 = Constants.RNG.nextInt(V);
        int i2 = Constants.RNG.nextInt(V - 1);
        if (i2 >= i1) {
            i2++;
        }
        if (i1 > i2) {
            int swap = i1;
            i1 = i2;
            i2 = swap;
        }
        final int a = (i1 - 1 + V) % V;
        final int b = i1;
        final int c = i2 - 1;
        final int d = i2;
        double deltaScore = -(calculatePartScore(a, b) + calculatePartScore(c, d)) + (calculatePartScore(a, c) + calculatePartScore(b, d));
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            reverse(types, i1, i2 - 1);
            reverse(indexes, i1, i2 - 1);
            saveBest();
        } else {
        }
    }

    private void swap() {
        final int V = types.size();
        int i1 = Constants.RNG.nextInt(V);
        int i2 = Constants.RNG.nextInt(V - 1);
        if (i2 >= i1) {
            i2++;
        }
        if (i1 > i2) {
            int swap = i1;
            i1 = i2;
            i2 = swap;
        }

        if (i1 == 0 && i2 == V - 1) {
            final int a = (i2 - 1 + V) % V;
            final int b = i2;
            final int e = i1;
            final int f = (i1 + 1) % V;
            final double before = calculatePartScore(a, b) + calculatePartScore(b, e) + calculatePartScore(e, f);
            final double after = calculatePartScore(a, e) + calculatePartScore(e, b) + calculatePartScore(b, f);
            double deltaScore = after - before;
            if (sa.accept(deltaScore)) {
                score += deltaScore;
                Collections.swap(types, i1, i2);
                Collections.swap(indexes, i1, i2);
                saveBest();
            } else {
            }
        } else if (i1 + 1 == i2) {
            final int a = (i1 - 1 + V) % V;
            final int b = i1;
            final int e = i2;
            final int f = (i2 + 1) % V;
            final double before = calculatePartScore(a, b) + calculatePartScore(b, e) + calculatePartScore(e, f);
            final double after = calculatePartScore(a, e) + calculatePartScore(e, b) + calculatePartScore(b, f);
            double deltaScore = after - before;
            if (sa.accept(deltaScore)) {
                score += deltaScore;
                Collections.swap(types, i1, i2);
                Collections.swap(indexes, i1, i2);
                saveBest();
            } else {
            }
        } else {
            final int a = (i1 - 1 + V) % V;
            final int b = i1;
            final int c = (i1 + 1) % V;
            final int d = (i2 - 1 + V) % V;
            final int e = i2;
            final int f = (i2 + 1) % V;
            final double before = calculatePartScore(a, b) + calculatePartScore(b, c) + calculatePartScore(d, e) + calculatePartScore(e, f);
            final double after = calculatePartScore(a, e) + calculatePartScore(e, c) + calculatePartScore(d, b) + calculatePartScore(b, f);
            double deltaScore = after - before;
            if (sa.accept(deltaScore)) {
                score += deltaScore;
                Collections.swap(types, i1, i2);
                Collections.swap(indexes, i1, i2);
                saveBest();
            } else {
            }
        }
    }

    private void insert() {
        int i1 = Constants.RNG.nextInt(types.size());
        int i2 = Constants.RNG.nextInt(types.size() - 1);
        int i3 = Constants.RNG.nextInt(types.size() - 2);
        if (i2 > i1) {
            i2++;
        }
        if (i3 > i1) {
            i3++;
        }
        if (i3 > i2) {
            i3++;
        }
        if (i1 > i2) {
            int swap = i1;
            i1 = i2;
            i2 = swap;
        }
        if (i1 > i3) {
            int swap = i1;
            i1 = i3;
            i3 = swap;
        }
        if (i2 > i3) {
            int swap = i2;
            i2 = i3;
            i3 = swap;
        }

        ArrayList<Integer> copyTypes = new ArrayList<>();
        ArrayList<Integer> copyIndexes = new ArrayList<>();
        for (int i = 0; i < types.size(); i++) {
            copyTypes.add(types.get(i));
            copyIndexes.add(indexes.get(i));
        }
        types.clear();
        indexes.clear();
        for (int i = 0; i < i1; i++) {
            types.add(copyTypes.get(i));
            indexes.add(copyIndexes.get(i));
        }
        for (int i = i2; i < i3; i++) {
            types.add(copyTypes.get(i));
            indexes.add(copyIndexes.get(i));
        }
        for (int i = i1; i < i2; i++) {
            types.add(copyTypes.get(i));
            indexes.add(copyIndexes.get(i));
        }
        for (int i = i3; i < copyTypes.size(); i++) {
            types.add(copyTypes.get(i));
            indexes.add(copyIndexes.get(i));
        }

        double deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            types.clear();
            indexes.clear();
            for (int i = 0; i < copyTypes.size(); i++) {
                types.add(copyTypes.get(i));
                indexes.add(copyIndexes.get(i));
            }
        }
    }

    private void moveISS() {
        final int i = Constants.RNG.nextInt(M);
        final int currentR2 = r2[i];
        final int currentC2 = c2[i];

        final int n = Constants.RNG.nextInt(N);

        final int random = Constants.RNG.nextInt(3);
        if (random == 0) {
            r2[i] = Constants.RNG.nextInt(1001);
            c2[i] = Constants.RNG.nextInt(1001);
        } else if (random == 1) {
            r2[i] = r[n];
            c2[i] = c[n];
        } else {
            r2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
            c2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
            r2[i] = Math.min(1000, Math.max(0, r2[i]));
            c2[i] = Math.min(1000, Math.max(0, c2[i]));
        }

        double deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            r2[i] = currentR2;
            c2[i] = currentC2;
        }
    }

    private void moveISS3() {
        final int i = Constants.RNG.nextInt(M);
        final int currentR2 = r2[i];
        final int currentC2 = c2[i];

        if (Constants.RNG.nextInt(2) == 0) {
            r2[i] = Constants.RNG.nextInt(1001);
            c2[i] = Constants.RNG.nextInt(1001);
        } else {
            r2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
            c2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
            r2[i] = Math.min(1000, Math.max(0, r2[i]));
            c2[i] = Math.min(1000, Math.max(0, c2[i]));
        }

        double deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            r2[i] = currentR2;
            c2[i] = currentC2;
        }
    }

    private void moveISS2() {
        final int i = Constants.RNG.nextInt(M);
        final int currentR2 = r2[i];
        final int currentC2 = c2[i];

        if (Constants.RNG.nextInt(2) == 0) {
            r2[i] = Constants.RNG.nextInt(1001);
            c2[i] = Constants.RNG.nextInt(1001);
        } else {
            r2[i] += -100 + Constants.RNG.nextInt(201);
            c2[i] += -100 + Constants.RNG.nextInt(201);
            r2[i] = Math.min(1000, Math.max(0, r2[i]));
            c2[i] = Math.min(1000, Math.max(0, c2[i]));
        }

        double deltaScore = calculateScore() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            saveBest();
        } else {
            r2[i] = currentR2;
            c2[i] = currentC2;
        }
    }

    private void addISS() {
        final int V = types.size();
        final int i = Constants.RNG.nextInt(V);
        final int index = Constants.RNG.nextInt(M);

        types.add(2);
        indexes.add(index);

        final int a = (i - 1 + V) % V;
        final int b = i;
        double deltaScore = -(calculatePartScore(a, b)) + (calculatePartScore(a, V) + calculatePartScore(V, b));
        Integer remove = types.remove(V);
        Integer remove2 = indexes.remove(V);
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            types.add(i, 2);
            indexes.add(i, index);
            saveBest();
        } else {
        }
    }

    private void addBestISS() {
        final int V = types.size();
        final int i = Constants.RNG.nextInt(V);

        double best = 1e99;
        int index = -1;
        for (int m = 0; m < M; m++) {
            types.add(2);
            indexes.add(m);

            final int a = (i - 1 + V) % V;
            final int b = i;

            double deltaScore = -(calculatePartScore(a, b)) + (calculatePartScore(a, V) + calculatePartScore(V, b));

            if (deltaScore < best) {
                best = deltaScore;
                index = m;
            }

            Integer remove = types.remove(V);
            Integer remove2 = indexes.remove(V);
        }

        if (sa.accept(best)) {
            score += best;
            types.add(i, 2);
            indexes.add(i, index);
            saveBest();
        } else {
        }
    }

    private void removeISS() {
        final int V = types.size();
        final int i = Constants.RNG.nextInt(V);
        if (types.get(i) != 2) {
            return;
        }
        final int a = (i - 1 + V) % V;
        final int b = i;
        final int c = (i + 1) % V;
        double deltaScore = -(calculatePartScore(a, b) + calculatePartScore(b, c)) + (calculatePartScore(a, c));
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            types.remove(i);
            indexes.remove(i);
            saveBest();
        } else {
        }
    }

    private void saveBest() {
        if (score < bestScore) {
            bestScore = score;
            for (int i = 0; i < M; i++) {
                bestR2[i] = r2[i];
                bestC2[i] = c2[i];
            }
            bestType.clear();
            bestIndex.clear();
            for (int i = 0; i < types.size(); i++) {
                bestType.add(types.get(i));
                bestIndex.add(indexes.get(i));
            }
        }
    }

    private double calculateScore() {
        double score = 0;
        final int V = types.size();
        for (int i = 0; i < V; i++) {
            score += calculatePartScore(i, (i + 1) % V);
        }
        return score;
    }

    private double calculatePartScore(int i, int j) {
        return alpha[types.get(i) + types.get(j)] * distance(getR(i), getC(i), getR(j), getC(j));
    }

    private int getR(int i) {
        return types.get(i) == 1 ? r[indexes.get(i)] : r2[indexes.get(i)];
    }

    private int getC(int i) {
        return types.get(i) == 1 ? c[indexes.get(i)] : c2[indexes.get(i)];
    }

    private double distance(int r, int c, int r2, int c2) {
        double dr = r - r2;
        double dc = c - c2;
        return dr * dr + dc * dc;
    }

    private void reverse(ArrayList<Integer> a, int i, int j) {
        for (int l = i, r = j; l < r; l++, r--) {
            Collections.swap(a, l, r);
        }
    }

    private void swap(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

}

final class Utils {
    private Utils() {
    }

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

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

}

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 ? Constants.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

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

    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() {
        double time0to1 = elapsedPercentage(startTime, endTime, time);
        double startY = startRange;
        double endY = endRange;
        range = interpolate(startY, endY, time0to1);
    }

    public void updateTime() {
        time = useTime ? Constants.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[Constants.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[Constants.RNG.nextInt() & 32767] < d) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

}

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;
    }
}

interface Constants {
    Watch watch = new Watch();
    PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());
}
yukicoder

結果

テストケース

ソースコード
