#783415 (Java21) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	Yu_212
提出日時	2022-07-30 17:57:59
言語	Java21 (openjdk 21)
結果	AC
実行時間	824 ms / 1,000 ms
コード長	20,876 bytes
コンパイル時間	3,238 ms
実行使用メモリ	73,888 KB
スコア	8,939,609
最終ジャッジ日時	2022-07-30 17:59:00
合計ジャッジ時間	28,287 ms
ジャッジサーバーID （参考情報）	judge10 / judge14
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	768 ms 73,184 KB
testcase_01	AC	723 ms 72,972 KB
testcase_02	AC	662 ms 73,572 KB
testcase_03	AC	823 ms 72,888 KB
testcase_04	AC	705 ms 73,504 KB
testcase_05	AC	758 ms 72,844 KB
testcase_06	AC	744 ms 73,220 KB
testcase_07	AC	714 ms 73,572 KB
testcase_08	AC	818 ms 73,488 KB
testcase_09	AC	759 ms 73,648 KB
testcase_10	AC	767 ms 73,832 KB
testcase_11	AC	762 ms 73,340 KB
testcase_12	AC	731 ms 73,032 KB
testcase_13	AC	710 ms 72,852 KB
testcase_14	AC	663 ms 73,604 KB
testcase_15	AC	733 ms 72,860 KB
testcase_16	AC	750 ms 72,956 KB
testcase_17	AC	704 ms 72,732 KB
testcase_18	AC	685 ms 73,476 KB
testcase_19	AC	751 ms 72,820 KB
testcase_20	AC	716 ms 72,896 KB
testcase_21	AC	824 ms 73,600 KB
testcase_22	AC	793 ms 73,724 KB
testcase_23	AC	728 ms 73,888 KB
testcase_24	AC	775 ms 73,132 KB
testcase_25	AC	752 ms 73,392 KB
testcase_26	AC	786 ms 72,844 KB
testcase_27	AC	749 ms 73,632 KB
testcase_28	AC	699 ms 73,880 KB
testcase_29	AC	724 ms 73,552 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    boolean isLocal;
    Random rand = new Random();
    In in = new In(System.in);
    PrintStream out = System.out;
    long inf = 0x1fffffffffffffffL;
    int iinf = 0x3fffffff;
    long startTime;

    private static final int s = 1001;
    private static final int n = 100;
    private static final int m = 8;
    Pos[] planets = new Pos[n];
    boolean[] grid = new boolean[s * s];
    int[][] dist = new int[n][n];
    int[][] neighbor = new int[n][n - 1];

    class St {
        private final Pos p;
        private final int upd;

        St(Pos p, int upd) {
            this.p = p;
            this.upd = upd;
        }
    }

    long solve(int seed) {
        startTime = System.currentTimeMillis();
        in();
        State state = initialState();
        while (!elapsed(300)) {
            state.optimize();
        }
        debug(state.ds);
        List<St> cand = new ArrayList<>();
        for (int i = 0; i < 8000; i++) {
            Pos p = pos(rand.next(s), rand.next(s));
            int upd = state.station(0, p, false);
//            debug(p, upd);
            if (upd > -300000) {
                continue;
            }
            cand.add(new St(p, upd));
        }
        debug(cand.size());
        int[] last = new int[m];
        for (St st : cand) {
            int best = 0;
            int bi = -1;
            for (int i = 0; i < m; i++) {
                int upd = state.station(i, st.p, false);
                if (best > upd) {
                    best = upd;
                    bi = i;
                }
                if (state.station[i] == null) {
                    break;
                }
            }
            if (bi != -1) {
                state.station(bi, st.p, true);
                last[bi] = st.upd;
            }
        }
        state.optAll();
        debug(last);
        debug(state.ds);
        answer(state);
        return isLocal ? Math.round(1000000000.0 / (Math.sqrt(state.ds) + 1000)) : 0;
    }

    void in() {
        Pos.init(1001, 1001);
        in.nextInt();
        in.nextInt();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            planets[i] = pos(a, b);
            grid[planets[i].z] = true;
        }
        IntStream.range(0, n).forEach(i -> {
            Integer[] a = new Integer[n - 1];
            Arrays.setAll(dist[i], j -> planets[i].dist(planets[j]) * 25);
            Arrays.setAll(a, j -> j < i ? j : j + 1);
            Arrays.sort(a, Comparator.comparingLong(j -> dist[i][j]));
            Arrays.setAll(neighbor[i], j -> a[j]);
        });
    }

    class State {
        double score;
        boolean hasScore;
        State prevCopy;
        int ds;
        int[] tour;
        int[] position;
        Pos[] station;
        int[] relay;
        int[] relay2;

        State(int[] tour, int[] position, int ds, int[] relay, int[] relay2, Pos[] station) {
            this.tour = tour;
            this.position = position;
            this.ds = ds;
            this.station = station;
            this.relay = relay;
            this.relay2 = relay2;
        }

        State(State prev) {
            this.score = prev.score;
            this.hasScore = true;
        }

        State rollback() {
            return prevCopy;
        }

        int neighbor0(double stage) {
            return 0;
        }

        int neighbor(double stage) {
            hasScore = false;
            prevCopy = copy();
            return neighbor0(stage);
        }

        State copy() {
            return new State(this);
        }

        boolean tryTwoOpt() {
            boolean updated = false;
            for (int i = 0; i < n; i++) {
                int a = tour[i];
                int b = tour[i + 1 < n ? i + 1 : 0];
                for (int k = 0; k < n - 1; k++) {
                    int j = position[neighbor[a][k]];
                    int c = tour[j];
                    int d = tour[j + 1 < n ? j + 1 : 0];
                    if (a == d || b == c) {
                        continue;
                    }
                    if (dist[a][c] > dist[a][b]) {
                        break;
                    }
                    long before = dist[a][b] + dist[c][d];
                    long after = dist[a][c] + dist[b][d];
                    if (after < before) {
                        twoOpt(i, j);
                        updated = true;
                        break;
                    }
                }
            }
            return updated;
        }

        void twoOpt(int i, int j) {
            if (i > j) {
                int temp = i;
                i = j;
                j = temp;
            }
            while (i + 1 < j) {
                i++;
                int temp = tour[i];
                tour[i] = tour[j];
                tour[j] = temp;
                position[tour[i]] = i;
                position[tour[j]] = j;
                j--;
            }
        }

        void doubleBridge() {
            int[] i = new int[4];
            do {
                Arrays.setAll(i, j -> rand.next(n));
                Arrays.sort(i);
            } while (!(i[0] + 1 < i[1] && i[1] + 1 < i[2] && i[2] + 1 < i[3] && (0 < i[0] || i[3] < n - 1)));
            int a = i[1] - i[0];
            int b = i[2] - i[1];
            int c = i[3] - i[2];
            int[] copy = Arrays.copyOfRange(tour, i[0] + 1, i[3] + 1);
            int k = i[0] + 1;
            for (int j = 0; j < c; j++) {
                tour[k + j] = copy[a + b + j];
                position[copy[a + b + j]] = k + j;
            }
            k += c;
            for (int j = 0; j < b; j++) {
                tour[k + j] = copy[a + j];
                position[copy[a + j]] = k + j;
            }
            k += b;
            for (int j = 0; j < a; j++) {
                tour[k + j] = copy[j];
                position[copy[j]] = k + j;
            }
        }

        void optimize() {
            int[] oldTour = tour.clone();
            int[] oldPosition = position.clone();
            doubleBridge();
            while (tryTwoOpt());
            int nds = calcDist();
            if (ds > nds) {
                ds = nds;
            } else {
                tour = oldTour;
                position = oldPosition;
            }
        }

        int station(int k, Pos p, boolean change) {
            Pos old = station[k];
            station[k] = p;
            int ods = ds;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += optRelay(i, change);
            }
            if (change) {
                ds = sum;
            } else {
                station[k] = old;
            }
            return sum - ods;
        }

        int optRelay(int i, boolean change) {
            int j = i == n - 1 ? 0 : i + 1;
            if (change) {
                relay[i] = -1;
                relay2[i] = -1;
            }
            int bi = -1;
            int bj = -1;
            int bid = iinf;
            int bjd = iinf;
            int min = dist[tour[i]][tour[j]];
            for (int k = 0; k < m; k++) {
                if (station[k] == null) {
                    break;
                }
                int di = planets[tour[i]].dist(station[k]) * 5;
                int dj = planets[tour[j]].dist(station[k]) * 5;
                int upd = di + dj;
                if (min > upd) {
                    min = upd;
                    if (change) {
                        relay[i] = n + k;
                        relay2[i] = -1;
                    }
                }
                if (bid > di) {
                    bid = di;
                    bi = k;
                }
                if (bjd > dj) {
                    bjd = dj;
                    bj = k;
                }
            }
            int b2 = bid + bjd + station[bi].dist(station[bj]);
            if (min > b2) {
                min = b2;
                if (change) {
                    relay[i] = n + bi;
                    relay2[i] = n + bj;
                }
            }
            return min;
        }

        void optAll() {
//            int ods = ds;
//            for (int k = 0; k < m; k++) {
//                int sx = 0;
//                int sy = 0;
//                int ss = 0;
//                for (int i = 0; i < n; i++) {
//                    int j = i == n - 1 ? 0 : i + 1;
//                    if (relay[i] == k + n) {
//                        Pos pi = planets[tour[i]];
//                        Pos pj = planets[tour[j]];
//                        sx += pi.x + pj.x;
//                        sy += pi.y + pj.y;
//                        ss += 2;
//                    }
//                }
//                station(k, pos(Math.round((float)sx / ss), Math.round((float)sy / ss)), true);
//            }
//            debug("!", ds - ods);
//            int sum = 0;
//            for (int i = 0; i < n; i++) {
//                sum += optRelay2(i);
//            }
//            debug("!!", sum - ds);
//            ds = sum;
            for (int i = 0; i < n; i++) {
                int j = i == n - 1 ? 0 : i + 1;
                if (relay[i] != -1) {
                    continue;
                }
                int min = dist[tour[i]][tour[j]];
                for (int k = 0; k < n; k++) {
                    if (tour[i] == k || tour[j] == k) {
                        continue;
                    }
                    int upd = dist[tour[i]][k] + dist[k][tour[j]];
                    if (min > upd) {
//                        debug("!" + k + ", " + (min - upd));
                        ds += upd - min;
                        min = upd;
                        relay[i] = k;
                    }
                }
            }
        }

        int calcDist() {
            int ds = 0;
            for (int i = 0; i < n; i++) {
                int j = i == n - 1 ? 0 : i + 1;
                ds += dist[tour[i]][tour[j]];
            }
            return ds;
        }

        double getScore() {
            if (!hasScore) {
                score = calcScore();
                hasScore = true;
            }
            return score;
        }

        double calcScore() {
            double score = 0;
            return score;
        }

        long realScore() {
            int score = 0;
            return score;
        }
    }

    State initialState() {
        int[] tour = new int[n];
        int[] position = new int[n];
        BitSet used = new BitSet(n);
        used.set(0);
        int ds = 0;
        int prev = 0;
        for (int i = 1; i < n; i++) {
            for (int k = 0; k < n - 1; k++) {
                int j = neighbor[prev][k];
                if (!used.get(j)) {
                    ds += dist[prev][j];
                    prev = j;
                    tour[i] = j;
                    position[j] = i;
                    used.set(j);
                    break;
                }
            }
        }
        Pos[] station = new Pos[m];
        int[] relay = new int[n];
        int[] relay2 = new int[n];
        Arrays.fill(relay, -1);
        Arrays.fill(relay2, -1);
        return new State(tour, position, ds, relay, relay2, station);
    }

    void answer(State state) {
        for (Pos pos : state.station) {
            if (pos == null) {
                out.println("0 0");
            } else {
                out.println(pos.x + " " + pos.y);
            }
        }
        int k = n + 1;
        for (int i = 0; i < n; i++) {
            if (state.relay[i] != -1) {
                k++;
            }
            if (state.relay2[i] != -1) {
                k++;
            }
        }
        out.println(k);
        for (int i = 0; i < n; i++) {
            out.println("1 " + (state.tour[i] + 1));
            if (state.relay[i] != -1) {
                if (state.relay[i] < n) {
                    out.println("1 " + (state.relay[i] + 1));
                } else {
                    out.println("2 " + (state.relay[i] - n + 1));
                }
                if (state.relay2[i] != -1) {
                    out.println("2 " + (state.relay2[i] - n + 1));
                }
            }
        }
        out.println("1 1");
    }

    void debug(Object... args) {
        if (!isLocal) {
            return;
        }
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        System.err.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
    }

    Pos pos(int x, int y) {
        return Pos.instances[y * s + x];
    }

    Pos pos(int z) {
        return Pos.instances[z];
    }

    static class Pos implements Comparable<Pos> {
        static Pos[] instances;
        static void init(int h, int w) {
            instances = new Pos[h * w];
            for (int i = 0; i < h * w; i++) {
                instances[i] = new Pos(i % w, i / w, i);
            }
        }

        final int x, y, z;

        private Pos(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        int dist(Pos o) {
            int xd = (x - o.x);
            int yd = (y - o.y);
            return xd * xd + yd * yd;
        }

        @Override
        public int compareTo(Pos o) {
            return Integer.compare(z, o.z);
        }

        @Override
        public boolean equals(Object o) {
            return o instanceof Pos && z == ((Pos)o).z;
        }

        @Override
        public int hashCode() {
            return z;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d)", x, y);
        }
    }

    State climbing(State state, long timeLimit) {
        timeLimit *= 1000000;
        long startTime = System.nanoTime();
        State bestState = state.copy();
        double bestScore = state.getScore();
        while (true) {
            long nowTime = System.nanoTime() - startTime;
            if (nowTime >= timeLimit) {
                break;
            }
            double prevScore = state.getScore();
            state.neighbor((double)nowTime / timeLimit);
            if (bestScore < state.getScore()) {
                bestScore = state.getScore();
                bestState = state.copy();
            }
            if (state.getScore() < prevScore) {
                state = state.rollback();
            }
        }
        return bestState;
    }

    State annealing(State state, double startTemp, double endTemp, long timeLimit) {
        State bestState = state.copy();
        double bestScore = state.getScore();
        while (true) {
            long nowTime = System.currentTimeMillis() - startTime;
            if (nowTime >= timeLimit) {
                break;
            }
            double prevScore = state.getScore();
            int nid = state.neighbor((double)nowTime / timeLimit);
            if (nid == -1) {
                continue;
            }
            if (bestScore < state.getScore()) {
                bestScore = state.getScore();
                bestState = state.copy();
            }
            double diff = state.getScore() - prevScore;
            double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit;
            double p = diff > 0 ? 1 : Math.exp(diff / temp);
            if (rand.nextDouble() >= p) {
                state = state.rollback();
            }
        }
        return bestState;
    }

    long elapsed() {
        return (long)((System.currentTimeMillis() - startTime) * (isLocal ? 1.7 : 1));
    }

    boolean elapsed(long timeLimit) {
        return elapsed() >= timeLimit;
    }

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

    static class Random {
        private long x, y, z, w;

        Random() {
            this(ThreadLocalRandom.current().nextLong());
        }

        Random(long seed) {
            this.x = seed;
            for (int i = 0; i < 20; i++) {
                rand();
            }
        }

        private long rand() {
            long t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ t ^ (t >>> 8);
            return x & 0x7fffffff;
        }

        long next() {
            return rand() << 31 | rand();
        }

        int next(int n) {
            return (int)(rand() % n);
        }

        int next(int l, int r) {
            return (int)(rand() % (r - l) + l);
        }

        double nextDouble() {
            return rand() / 2147483647.0;
        }
    }

    static class In {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        public In(InputStream input) {
            this.reader = new BufferedReader(new InputStreamReader(input), 0x10000);
        }

        String next() {
            try {
                while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
            } catch (IOException ignored) {
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char[] nextCharArray() {
            return next().toCharArray();
        }

        String[] nextStringArray(int n) {
            String[] s = new String[n];
            for (int i = 0; i < n; i++) {
                s[i] = next();
            }
            return s;
        }

        char[][] nextCharGrid(int n, int m) {
            char[][] a = new char[n][m];
            for (int i = 0; i < n; i++) {
                a[i] = next().toCharArray();
            }
            return a;
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        int[] nextIntArray(int n, IntUnaryOperator op) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsInt(nextInt());
            }
            return a;
        }

        int[][] nextIntMatrix(int h, int w) {
            int[][] a = new int[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextIntArray(w);
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextLong();
            }
            return a;
        }

        long[] nextLongArray(int n, LongUnaryOperator op) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = op.applyAsLong(nextLong());
            }
            return a;
        }

        long[][] nextLongMatrix(int h, int w) {
            long[][] a = new long[h][w];
            for (int i = 0; i < h; i++) {
                a[i] = nextLongArray(w);
            }
            return a;
        }

        List<List<Integer>> nextEdges(int n, int m, boolean directed) {
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                res.add(new ArrayList<>());
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                res.get(u).add(v);
                if (!directed) {
                    res.get(v).add(u);
                }
            }
            return res;
        }
    }
}
yukicoder

結果

テストケース

ソースコード
