結果
問題 | No.5015 Escape from Labyrinth |
ユーザー |
![]() |
提出日時 | 2023-04-16 18:42:30 |
言語 | Java (openjdk 23) |
結果 |
RE
|
実行時間 | - |
コード長 | 26,589 bytes |
コンパイル時間 | 3,664 ms |
コンパイル使用メモリ | 95,912 KB |
実行使用メモリ | 74,272 KB |
スコア | 178,290 |
最終ジャッジ日時 | 2023-04-16 18:47:27 |
合計ジャッジ時間 | 292,881 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 99 RE * 1 |
ソースコード
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;int[][] beam = new int[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);if (cur == null || grid[cur.z] == '#') {break;}for (int j = 0; j < 60; j += ds[i]) {beam[j][cur.z]++;}}}}for (int i = 0; i < N * N; i++) {int c = 1;for (int j = 0; j < 60; j++) {if (beam[j][i] > 0) {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];// 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 (routes.size() >= 200) {// break;// }//// if (dsum + bd * MUL[D] >= 60 * 500) {////// c++;////// if (c >= 100) {////// break;////// } else {////// continue;////// }//// continue;//// }// visited.set(p);// dsum += bd;// routes.add(bi, p);// }debug("?", elapsed());State result = annealing(new State(), 180*10, 180, 2500);List<Integer> routes = result.routes;debug("?", elapsed());Pos p = jps[J];int tt = 0;int ds1 = 0;int ds2 = 0;totalCost = 0;List<Result> results = new ArrayList<>();BitSet aa = new BitSet(J);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.damage, (tt+res.time)%60);results.add(res);tt = (tt + res.time) % 60;p = res.to;if (i > 1 && aa.get(routes.get(i - 1))) {debug("!!");throw new RuntimeException();}aa.set(routes.get(i - 1));}debug(D, result.dsum, ds1, result.dsum/60, ds1/60, ds2, ds2*60./result.dsum);if (ds2 >= 1500) {throw new RuntimeException();// debug("!!!!");// p = jps[J];// tt = 0;// int dm = 0;// for (Result res : results) {// if (res.from == jps[J + 1]) {// Result v = route(res.from, jps[J + 2], tt);// v.out(p, tt);// break;// }// dm += res.damage;// res.out(p, tt);// tt = (tt + res.time) % 60;// p = res.to;// }} else {p = jps[J];tt = 0;for (Result res : results) {res.out(p, tt);tt = (tt + res.time) % 60;p = res.to;}}debug(ds2, 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);}//1678int 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;// }public static final double[] MUL = {0, 0, 0, 1.25, 1.33, 1.4, 1.6, 1.8};class State {BitSet visited = new BitSet(J + 3);List<Integer> routes = new ArrayList<>();int dsum;double score;boolean hasScore;State prevCopy;State() {visited.set(J);visited.set(J + 1);visited.set(J + 2);routes.add(J);routes.add(J + 1);routes.add(J + 2);dsum = distances[J][J+1] + distances[J+1][J+2];}State(State prev) {this.visited = (BitSet)prev.visited.clone();this.routes = new ArrayList<>(prev.routes);this.dsum = prev.dsum;this.score = prev.score;this.hasScore = true;}int real() {int damage = 0;int tt = 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);damage += res.damage;// debug(p, res.from, res.to, res.damage);tt = (tt + res.time) % 60;}return damage;}State rollback() {return prevCopy;}int neighbor0(double stage) {while (true) {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;}visited.set(p);dsum += bd;routes.add(bi, p);score = calcScore(0);break;}return 0;}int neighbor1(double stage) {int bd = -iinf;int bp = 0;for (int p = 1; p + 1 < routes.size(); p++) {int f = routes.get(p - 1);int t = routes.get(p + 1);int r = routes.get(p);if (r >= J) {continue;}int diff = distances[f][r] + distances[r][t] - distances[f][t];if (bd < diff) {bd = diff;bp = p;}}visited.clear(routes.get(bp));dsum -= bd;routes.remove(bp);score = calcScore(0);return 1;}int neighbor(double stage, double rs) {hasScore = false;prevCopy = copy();if (routes.size() >= 180 && rand.next(5) < 2 || dsum * MUL[D] >= 60 * 1000 * rs) {// debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 1);return neighbor1(stage);} else {// debug(dsum * MUL[D], getScore(stage), routes.size(), 36000, 0);return neighbor0(stage);}}State copy() {return new State(this);}double getScore(double stage) {if (!hasScore) {score = calcScore(stage);hasScore = true;}return score;}double calcScore(double stage) {double score = (routes.size() - 3) * 180*5 - dsum * MUL[D];return score;}long realScore() {int score = 0;return score;}}State annealing(State state, double startTemp, double endTemp, long timeLimit) {State bestState = state.copy();double bestScore = state.getScore(0);int itr = 0;int rb = 0;int c0 = 0;double rs = 1;boolean calc = false;while (true) {long nowTime = System.currentTimeMillis() - startTime;if (nowTime >= timeLimit) {break;}double stage = (double)nowTime / timeLimit;if (stage > 0.9 && !calc) {calc = true;rs = 1350. / state.real();debug("??", rs);}itr++;double prevScore = state.getScore(stage);double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit;double thres = prevScore + rand.nextLog() * temp;int nid = state.neighbor(stage, rs);if (nid == -1) {continue;}if (nid == 0) {c0++;}if (bestScore < state.getScore(stage)) {bestScore = state.getScore(stage);bestState = state.copy();}if (state.getScore(stage) <= thres) {state = state.rollback();rb++;}}debug(itr, rb, c0);return bestState;}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;totalCost += D * beam[tt][p.z];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 + v.p.dist(g)));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;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;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++) { // LURDint 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);}@Overridepublic int compareTo(Pos o) {return Integer.compare(z, o.z);}@Overridepublic boolean equals(Object o) {return o instanceof Pos && z == ((Pos)o).z;}@Overridepublic int hashCode() {return z;}@Overridepublic String toString() {return String.format("(%d, %d)", x, y);}}static void debug(Object... args) {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 a, b, c, d;Random() {this(ThreadLocalRandom.current().nextLong());}Random(long seed) {this.a = seed;for (int i = 0; i < 20; i++) {rand();}}private int rand() {long t = a ^ (a << 11);a = b;b = c;c = d;d = d ^ (d >>> 19) ^ t ^ (t >>> 8);return (int)(a & 0x7fffffff);}long next() {return (long)rand() << 31 | rand();}int next(int n) {return rand() % n;}int next(int l, int r) {return rand() % (r - l) + l;}double nextDouble() {return rand() / 2147483648.0;}double nextLog() {return Math.log(rand() + 1) - 21.487562597358306;}}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;}}}