結果

問題 No.5015 Escape from Labyrinth
ユーザー Yu_212Yu_212
提出日時 2023-04-16 15:19:13
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 19,713 bytes
コンパイル時間 3,489 ms
コンパイル使用メモリ 89,016 KB
実行使用メモリ 71,776 KB
スコア 95,490
最終ジャッジ日時 2023-04-16 15:23:16
合計ジャッジ時間 240,529 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,282 ms
69,868 KB
testcase_01 AC 2,285 ms
69,884 KB
testcase_02 AC 2,284 ms
69,348 KB
testcase_03 AC 2,288 ms
69,272 KB
testcase_04 AC 2,311 ms
69,308 KB
testcase_05 AC 2,285 ms
69,256 KB
testcase_06 AC 2,288 ms
69,572 KB
testcase_07 AC 2,297 ms
69,668 KB
testcase_08 AC 2,291 ms
69,584 KB
testcase_09 AC 2,299 ms
69,568 KB
testcase_10 AC 2,285 ms
69,788 KB
testcase_11 AC 2,286 ms
69,540 KB
testcase_12 AC 2,290 ms
69,592 KB
testcase_13 WA -
testcase_14 AC 2,314 ms
69,692 KB
testcase_15 AC 2,281 ms
69,764 KB
testcase_16 AC 2,313 ms
69,648 KB
testcase_17 AC 2,305 ms
69,740 KB
testcase_18 AC 2,310 ms
69,964 KB
testcase_19 WA -
testcase_20 AC 2,285 ms
69,468 KB
testcase_21 AC 2,279 ms
68,772 KB
testcase_22 AC 2,289 ms
69,520 KB
testcase_23 AC 2,422 ms
69,444 KB
testcase_24 WA -
testcase_25 AC 2,293 ms
68,840 KB
testcase_26 AC 2,283 ms
69,092 KB
testcase_27 AC 2,292 ms
68,888 KB
testcase_28 AC 2,293 ms
69,440 KB
testcase_29 AC 2,289 ms
69,288 KB
testcase_30 AC 2,282 ms
67,592 KB
testcase_31 AC 2,279 ms
69,424 KB
testcase_32 AC 2,287 ms
68,004 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 2,278 ms
69,336 KB
testcase_36 AC 2,294 ms
69,444 KB
testcase_37 AC 2,290 ms
70,120 KB
testcase_38 AC 2,300 ms
70,008 KB
testcase_39 AC 2,300 ms
69,584 KB
testcase_40 AC 2,284 ms
69,056 KB
testcase_41 AC 2,298 ms
69,688 KB
testcase_42 AC 2,321 ms
69,700 KB
testcase_43 AC 2,290 ms
69,488 KB
testcase_44 AC 2,303 ms
69,856 KB
testcase_45 AC 2,297 ms
69,808 KB
testcase_46 AC 2,287 ms
69,232 KB
testcase_47 AC 2,286 ms
69,232 KB
testcase_48 WA -
testcase_49 WA -
testcase_50 AC 2,289 ms
69,988 KB
testcase_51 AC 2,304 ms
69,664 KB
testcase_52 AC 2,292 ms
69,268 KB
testcase_53 AC 2,289 ms
69,520 KB
testcase_54 WA -
testcase_55 AC 2,311 ms
69,024 KB
testcase_56 AC 2,292 ms
69,708 KB
testcase_57 AC 2,292 ms
69,584 KB
testcase_58 AC 2,298 ms
68,968 KB
testcase_59 AC 2,286 ms
69,304 KB
testcase_60 AC 2,287 ms
69,328 KB
testcase_61 AC 2,282 ms
69,364 KB
testcase_62 AC 2,309 ms
69,160 KB
testcase_63 AC 2,305 ms
69,416 KB
testcase_64 WA -
testcase_65 AC 2,283 ms
69,224 KB
testcase_66 AC 2,291 ms
69,560 KB
testcase_67 AC 2,286 ms
71,396 KB
testcase_68 AC 2,289 ms
70,292 KB
testcase_69 AC 2,285 ms
69,660 KB
testcase_70 AC 2,285 ms
69,404 KB
testcase_71 AC 2,304 ms
70,000 KB
testcase_72 AC 2,289 ms
69,520 KB
testcase_73 AC 2,294 ms
69,528 KB
testcase_74 AC 2,329 ms
69,672 KB
testcase_75 AC 2,284 ms
67,864 KB
testcase_76 AC 2,288 ms
69,668 KB
testcase_77 AC 2,284 ms
69,780 KB
testcase_78 AC 2,293 ms
69,296 KB
testcase_79 AC 2,306 ms
69,204 KB
testcase_80 AC 2,286 ms
69,272 KB
testcase_81 AC 2,279 ms
69,252 KB
testcase_82 AC 2,283 ms
71,776 KB
testcase_83 AC 2,294 ms
69,812 KB
testcase_84 WA -
testcase_85 AC 2,295 ms
69,328 KB
testcase_86 AC 2,305 ms
69,316 KB
testcase_87 AC 2,285 ms
69,324 KB
testcase_88 AC 2,301 ms
69,512 KB
testcase_89 AC 2,287 ms
69,668 KB
testcase_90 AC 2,291 ms
69,284 KB
testcase_91 AC 2,274 ms
69,544 KB
testcase_92 AC 2,293 ms
69,420 KB
testcase_93 AC 2,329 ms
69,756 KB
testcase_94 AC 2,300 ms
69,040 KB
testcase_95 AC 2,292 ms
69,076 KB
testcase_96 AC 2,289 ms
69,964 KB
testcase_97 AC 2,287 ms
69,632 KB
testcase_98 AC 2,316 ms
69,844 KB
testcase_99 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 * 700) {
//                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);
        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;
        }
    }
}
0