#860221 (Java21) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	Yu_212
提出日時	2023-04-16 15:24:45
言語	Java21 (openjdk 21)
結果	AC
実行時間	2,361 ms / 3,000 ms
コード長	19,797 bytes
コンパイル時間	3,050 ms
コンパイル使用メモリ	94,276 KB
実行使用メモリ	71,360 KB
スコア	75,360
最終ジャッジ日時	2023-04-16 15:28:49
合計ジャッジ時間	238,153 ms
ジャッジサーバーID （参考情報）	judge14 / judge16
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2,287 ms 69,176 KB
testcase_01	AC	2,268 ms 68,860 KB
testcase_02	AC	2,271 ms 69,104 KB
testcase_03	AC	2,277 ms 69,312 KB
testcase_04	AC	2,284 ms 68,752 KB
testcase_05	AC	2,273 ms 69,772 KB
testcase_06	AC	2,282 ms 69,952 KB
testcase_07	AC	2,278 ms 68,924 KB
testcase_08	AC	2,273 ms 69,232 KB
testcase_09	AC	2,271 ms 71,360 KB
testcase_10	AC	2,274 ms 69,292 KB
testcase_11	AC	2,285 ms 69,620 KB
testcase_12	AC	2,281 ms 69,676 KB
testcase_13	AC	2,277 ms 69,436 KB
testcase_14	AC	2,361 ms 69,752 KB
testcase_15	AC	2,269 ms 69,592 KB
testcase_16	AC	2,282 ms 69,460 KB
testcase_17	AC	2,273 ms 69,472 KB
testcase_18	AC	2,292 ms 68,952 KB
testcase_19	AC	2,281 ms 69,384 KB
testcase_20	AC	2,283 ms 69,352 KB
testcase_21	AC	2,278 ms 69,260 KB
testcase_22	AC	2,270 ms 69,416 KB
testcase_23	AC	2,272 ms 67,728 KB
testcase_24	AC	2,270 ms 70,196 KB
testcase_25	AC	2,278 ms 69,684 KB
testcase_26	AC	2,266 ms 69,104 KB
testcase_27	AC	2,285 ms 69,388 KB
testcase_28	AC	2,269 ms 69,204 KB
testcase_29	AC	2,277 ms 69,864 KB
testcase_30	AC	2,269 ms 69,544 KB
testcase_31	AC	2,271 ms 68,940 KB
testcase_32	AC	2,289 ms 69,080 KB
testcase_33	AC	2,271 ms 68,692 KB
testcase_34	AC	2,263 ms 69,188 KB
testcase_35	AC	2,269 ms 69,120 KB
testcase_36	AC	2,277 ms 70,116 KB
testcase_37	AC	2,289 ms 69,216 KB
testcase_38	AC	2,281 ms 69,248 KB
testcase_39	AC	2,276 ms 68,960 KB
testcase_40	AC	2,265 ms 69,152 KB
testcase_41	AC	2,269 ms 69,604 KB
testcase_42	AC	2,260 ms 69,408 KB
testcase_43	AC	2,270 ms 69,728 KB
testcase_44	AC	2,290 ms 69,736 KB
testcase_45	AC	2,267 ms 69,052 KB
testcase_46	AC	2,285 ms 69,096 KB
testcase_47	AC	2,266 ms 69,772 KB
testcase_48	AC	2,271 ms 69,580 KB
testcase_49	AC	2,317 ms 67,692 KB
testcase_50	AC	2,290 ms 67,848 KB
testcase_51	AC	2,276 ms 69,336 KB
testcase_52	AC	2,267 ms 69,296 KB
testcase_53	AC	2,267 ms 69,764 KB
testcase_54	AC	2,268 ms 69,700 KB
testcase_55	AC	2,270 ms 69,112 KB
testcase_56	AC	2,282 ms 69,136 KB
testcase_57	AC	2,259 ms 69,144 KB
testcase_58	AC	2,285 ms 71,108 KB
testcase_59	AC	2,266 ms 69,544 KB
testcase_60	AC	2,274 ms 69,164 KB
testcase_61	AC	2,262 ms 69,084 KB
testcase_62	AC	2,290 ms 69,752 KB
testcase_63	AC	2,268 ms 69,208 KB
testcase_64	AC	2,290 ms 69,496 KB
testcase_65	AC	2,269 ms 69,464 KB
testcase_66	AC	2,277 ms 69,232 KB
testcase_67	AC	2,266 ms 69,180 KB
testcase_68	AC	2,276 ms 69,784 KB
testcase_69	AC	2,288 ms 69,320 KB
testcase_70	AC	2,270 ms 69,444 KB
testcase_71	AC	2,264 ms 69,308 KB
testcase_72	AC	2,270 ms 69,244 KB
testcase_73	AC	2,271 ms 69,404 KB
testcase_74	AC	2,280 ms 69,556 KB
testcase_75	AC	2,267 ms 70,216 KB
testcase_76	AC	2,286 ms 69,144 KB
testcase_77	AC	2,278 ms 69,588 KB
testcase_78	AC	2,273 ms 69,384 KB
testcase_79	AC	2,267 ms 69,112 KB
testcase_80	AC	2,264 ms 69,056 KB
testcase_81	AC	2,260 ms 69,352 KB
testcase_82	AC	2,269 ms 69,200 KB
testcase_83	AC	2,259 ms 69,068 KB
testcase_84	AC	2,288 ms 69,488 KB
testcase_85	AC	2,266 ms 69,232 KB
testcase_86	AC	2,273 ms 69,496 KB
testcase_87	AC	2,290 ms 69,096 KB
testcase_88	AC	2,273 ms 69,068 KB
testcase_89	AC	2,274 ms 69,576 KB
testcase_90	AC	2,286 ms 69,392 KB
testcase_91	AC	2,283 ms 69,040 KB
testcase_92	AC	2,269 ms 69,256 KB
testcase_93	AC	2,265 ms 69,452 KB
testcase_94	AC	2,267 ms 69,284 KB
testcase_95	AC	2,270 ms 69,576 KB
testcase_96	AC	2,289 ms 69,400 KB
testcase_97	AC	2,267 ms 69,436 KB
testcase_98	AC	2,268 ms 69,448 KB
testcase_99	AC	2,273 ms 69,140 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;

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

    public static final int N = 60;
    public int D;
    public static final int H = 1500;
    public int M;
    public int J;
    public char[] grid;
    public Pos[] ps;
    public int[] ds;
    public Pos[] jps;
    int[][] distances;
    boolean[][] beam = new boolean[60][N * N];
    int[] avgWait = new int[N * N];
    int[] jid = new int[N * N];
    public static final String[] ss = {"M L", "M U", "M R", "M D", "S"};
    long solve(int seed) {
        startTime = System.currentTimeMillis();
        in();
        distances = new int[J+3][J+3];
        for (int i = 0; i < J + 3; i++) {
            Arrays.fill(distances[i], iinf);
        }
        for (int i = 0; i < M; i++) {
            for (int d = 0; d < 4; d++) {
                Pos cur = ps[i];
                while (true) {
                    cur = cur.moved((d+2)%4);
                    if (cur == null || grid[cur.z] == '#') {
                        break;
                    }
                    for (int j = 0; j < 60; j += ds[i]) {
                        beam[j][cur.z] = true;
                    }
                }
            }
        }
        for (int i = 0; i < N * N; i++) {
            int c = 1;
            for (int j = 0; j < 60; j++) {
                if (beam[j][i]) {
                    c++;
                } else {
                    c = 1;
                }
                avgWait[i] += c;
            }
        }
        for (int i = 0; i < J + 3; i++) {
            calcDist(i);
        }
        BitSet visited = new BitSet(J + 3);
        visited.set(J);
        visited.set(J + 1);
        visited.set(J + 2);
        List<Integer> routes = new ArrayList<>();
        routes.add(J);
        routes.add(J + 1);
        routes.add(J + 2);
        int dsum = distances[J][J+1] + distances[J+1][J+2];
        double[] mul = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8};
        int c = 0;
        while (elapsed() < 2000) {
            int p;
            do {
                p = rand.next(0, J);
            } while (visited.get(p));
            int bi = -1;
            int bd = iinf;
            for (int i = 1; i < routes.size(); i++) {
                int f = routes.get(i - 1);
                int t = routes.get(i);
                int diff = distances[f][p] + distances[p][t] - distances[f][t];
                if (bd > diff) {
                    bd = diff;
                    bi = i;
                }
            }
            if (bi == -1) {
                continue;
            }
//            debug(p, bi, bd, dsum);
            if (dsum + bd * mul[D] >= 60 * 500) {
//                c++;
//                if (c >= 100) {
//                    break;
//                } else {
//                    continue;
//                }
                continue;
            }
            visited.set(p);
            dsum += bd;
            routes.add(bi, p);
        }
        Pos p = jps[J];
        int tt = 0;
        int ds1 = 0;
        int ds2 = 0;
        for (int i = 1; i < routes.size(); i++) {
            Result res = route(jps[routes.get(i - 1)], jps[routes.get(i)], tt);
//            debug(distances[routes.get(i - 1)][routes.get(i)], res.damage * 60);
            ds1 += distances[routes.get(i - 1)][routes.get(i)];
            ds2 += res.damage;
//            debug(p, res.from, res.to);
            res.out(p, tt);
            tt = (tt + res.time) % 60;
            p = res.to;
        }
        debug(D, dsum, ds1, dsum/60, ds1/60, ds2, ds2*60./dsum);
        if (ds2 > 1400) {
            debug("!");
        }
        debug(totalCost, routes.size() * 10);
        if (totalCost > 1500) {
            throw new RuntimeException();
        }
        return routes.size() * 10L;
//        List<Result> routes = new ArrayList<>();
//        routes.add(route(jps[J], jps[J + 1], 0));
//        routes.add(route(jps[J + 1], jps[J + 2], routes.get(0).time));
//        int dsum = routes.get(0).damage + routes.get(1).damage;
//        while (true) {
//            int p;
//            do {
//                p = rand.next(0, J);
//            } while (visited.get(p));
//            int tt = 0;
//            int bi = 0;
//            int bd = iinf;
//            Result br1 = null, br2 = null;
//            for (int i = 0; i < routes.size(); i++) {
//                Result r = routes.get(i);
//                Result r1 = route(r.from, jps[p], tt);
//                Result r2 = route(jps[p], r.to, (tt + r.time) % 60);
//                int diff = r1.damage + r2.damage - r.damage;
//                if (bd > diff) {
//                    bd = diff;
//                    bi = i;
//                    br1 = r1;
//                    br2 = r2;
//                }
//                tt = (tt + r.time) % 60;
//            }
//            debug(p, bi, bd, dsum);
//            if (dsum + bd >= 700) {
//                break;
//            }
//            visited.set(p);
//            dsum += bd;
//            routes.set(bi, br1);
//            routes.add(bi + 1, br2);
//        }
//        Pos p = jps[J];
//        int tt = 0;
//        for (Result res : routes) {
//            debug(p, res.from, res.to);
//            res.out(p, tt);
//            tt = (tt + res.time) % 60;
//            p = res.to;
//        }
//        visited.set(J + 2);
//        visited.set(J);
//        tt = moveTo(J, J+1, tt, visited);
//        visited.clear(J + 2);
//        tt = moveTo(J+1, J+2, tt, visited);
    }

    int totalCost = 0;
//    int moveTo(int s, int g, int tt, BitSet visited) {
//        int cur = s;
//        int ds = 0;
//        while (cur != g) {
//            int md = iinf;
//            int mi = -1;
//            for (int i = 0; i < J + 3; i++) {
//                if (visited.get(i)) {
//                    continue;
//                }
////                debug(i, cur, jps[i].dist(jps[g]), distances[cur * (J + 3) + i]);
//                int d = distances[cur * (J + 3) + i] + jps[i].dist(jps[g]) * 50;
//                if (md > d) {
//                    md = d;
//                    mi = i;
//                }
//            }
//            ds += distances[cur * (J + 3) + mi];
//            visited.set(mi);
//            tt = moveStraight(cur, mi, tt);
//            cur = mi;
//        }
//        debug(ds, totalCost);
//        return tt;
//    }

    class Result {
        List<Integer> route;
        int damage;
        int time;
        Pos from;
        Pos to;

        public Result(List<Integer> route, int damage, Pos from, Pos to) {
            this.route = route;
            this.damage = damage;
            this.time = route.size() % 60;
            this.from = from;
            this.to = to;
        }

        public void out(Pos p, int tt) {
            for (int v : route) {
                if (v < 4) p = p.moved(v);
                tt = (tt + 1) % 60;
                if (beam[tt][p.z]) {
                    totalCost += D;
                }
                totalCost++;
                out.println(ss[v]);
            }
        }
    }
    Result route(Pos s, Pos g, int tt) {
        class S {
            private final Pos p;
            private final int t;
            private final int d;

            public S(Pos p, int t, int d) {
                this.p = p;
                this.t = t;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(s, tt, 0));
        int[][] dist = new int[60][N * N];
        int[][] prev = new int[60][N * N];
        for (int i = 0; i < 60; i++) {
            Arrays.fill(dist[i], iinf);
            Arrays.fill(prev[i], -1);
        }
        dist[tt][s.z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.t][v.p.z] < v.d) {
                continue;
            }
            if (v.p.z == g.z) {
                List<Integer> route = new ArrayList<>();
                Pos cur = v.p;
                int ct = v.t;
                int damage = dist[ct][cur.z];
                while (prev[ct][cur.z] != -1) {
                    route.add(prev[ct][cur.z]);
                    if (prev[ct][cur.z] < 4) {
                        cur = cur.moved((prev[ct][cur.z] + 2) % 4);
                    }
                    ct = (ct + 59) % 60;
                }
                Collections.reverse(route);
                return new Result(route, damage, s, g);
            }
            int nt = (v.t + 1) % 60;
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.t][v.p.z] + 1 + (beam[nt][q.z] ? D : 0);
                if (dist[nt][q.z] > cost) {
                    dist[nt][q.z] = cost;
                    prev[nt][q.z] = d;
                    queue.add(new S(q, nt, cost));
                }
            }
            int cost = dist[v.t][v.p.z] + 1 + (beam[nt][v.p.z] ? D : 0);
            if (dist[nt][v.p.z] > cost) {
                dist[nt][v.p.z] = cost;
                prev[nt][v.p.z] = 4;
                queue.add(new S(v.p, nt, cost));
            }
        }
        throw new RuntimeException();
    }

    void calcDist(int s) {
        class S {
            private final Pos p;
            private final int d;

            public S(Pos p, int d) {
                this.p = p;
                this.d = d;
            }
        }
        PriorityQueue<S> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.d));
        queue.add(new S(jps[s], 0));
        int[] dist = new int[N * N];
        Arrays.fill(dist, iinf);
        dist[jps[s].z] = 0;
        while (!queue.isEmpty()) {
            S v = queue.remove();
            if (dist[v.p.z] < v.d) {
                continue;
            }
            if (jid[v.p.z] != -1) {
                distances[s][jid[v.p.z]] = v.d;
            }
            for (int d = 0; d < 4; d++) {
                Pos q = v.p.moved(d);
                if (q == null || grid[q.z] == '#') {
                    continue;
                }
                int cost = dist[v.p.z] + avgWait[q.z];
                if (dist[q.z] > cost) {
                    dist[q.z] = cost;
                    queue.add(new S(q, cost));
                }
            }
        }
    }

    void in() {
        in.nextInt();
        D = in.nextInt();
        in.nextInt();
        grid = new char[N * N];
        int jc = 0;
        for (int i = 0; i < N; i++) {
            char[] s = in.nextCharArray();
            for (int j = 0; j < N; j++) {
                grid[i * N + j] = s[j];
                if (grid[i * N + j] == 'J') {
                    jc++;
                }
            }
        }
        M = in.nextInt();
        J = jc;
        jps = new Pos[J + 3];
        ps = new Pos[M];
        ds = new int[M];
        for (int i = 0; i < M; i++) {
            int y = in.nextInt();
            int x = in.nextInt();
            int d = in.nextInt();
            ps[i] = pos(x, y);
            ds[i] = d;
        }
        jc = 0;
        Arrays.fill(jid, -1);
        for (int i = 0; i < N * N; i++) {
            if (grid[i] == 'S') {
                jps[J] = pos(i);
                jid[i] = J;
                grid[i] = '.';
            } else if (grid[i] == 'K') {
                jps[J + 1] = pos(i);
                jid[i] = J + 1;
                grid[i] = '.';
            } else if (grid[i] == 'G') {
                jps[J + 2] = pos(i);
                jid[i] = J + 2;
                grid[i] = '.';
            } else if (grid[i] == 'J') {
                jid[i] = jc;
                jps[jc++] = pos(i);
            } else if (grid[i] == 'E') {
                grid[i] = '#';
            }
        }
    }

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

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

    static class Timing {
        Pos p;
        int t, z;

        public Timing(Pos p, int t) {
            this.p = p;
            this.t = t;
            this.z = p.z * 60 + t;
        }
    }

    static class Pos implements Comparable<Pos> {
        static Pos[] instances;
        static Pos[] moved;
        static {
            instances = new Pos[N * N];
            moved = new Pos[4 * N * N];
            for (int i = 0; i < N * N; i++) {
                instances[i] = new Pos(i % N, i / N, i);
            }
            for (int i = 0; i < N * N; i++) {
                for (int d = 0; d < 4; d++) { // LURD
                    int nx = i % N + (d - 1) % 2;
                    int ny = i / N + (d - 2) % 2;
                    if (0 <= nx && nx < N && 0 <= ny && ny < N) {
                        moved[i * 4 + d] = instances[ny * N + nx];
                    }
                }
            }
        }

        final int x, y, z;

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

        Pos moved(int d) {
            return moved[z * 4 + d];
        }

        int dist(Pos o) {
            return Math.abs(x - o.x) + Math.abs(y - o.y);
        }

        Pos[] neighbors() {
            Pos[] p = new Pos[4];
            int i = 0;
            if ((p[i] = moved(0)) != null) i++;
            if ((p[i] = moved(1)) != null) i++;
            if ((p[i] = moved(2)) != null) i++;
            if ((p[i] = moved(3)) != null) i++;
            return i == 4 ? p : Arrays.copyOf(p, i);
        }

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

    static 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(" ")));
    }

    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;

        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

結果

テストケース

ソースコード