結果
| 問題 | No.5015 Escape from Labyrinth |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2023-04-16 14:46:57 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,974 ms / 3,000 ms |
| コード長 | 31,464 bytes |
| コンパイル時間 | 5,268 ms |
| コンパイル使用メモリ | 90,572 KB |
| 実行使用メモリ | 68,504 KB |
| スコア | 116,310 |
| 最終ジャッジ日時 | 2023-04-16 14:52:10 |
| 合計ジャッジ時間 | 307,909 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Scanner;public class Main {private static final int grid_size = 60;private static final int max_hp = 1500;private static final int[] dy = { -1, 1, 0, 0 };private static final int[] dx = { 0, 0, -1, 1 };private static final char[] dir = "UDLR".toCharArray();private static final int inf = (int) 1e9;private static final int[] dr = { -1, 0, 0, 1, };private static final int[] dc = { 0, -1, 1, 0, };private static final int EMPTY = 0;private static final int WALL = 1;private static final int JEWEL = 2;private static final int GUNPOWDER = 3;private static final int DETECTOR = 4;private static final int BLOCK = 5;private int N;private int D;private int H;private int[][] map;private int sr;private int sc;private int gr;private int gc;private int kr;private int kc;private int sumDistance;private ArrayList<Point> points = new ArrayList<>();private int bestSumDistance;private ArrayList<Point> bestPoints = new ArrayList<>();private ArrayList<Point> removedPoints = new ArrayList<>();private int thresholdDistance;private int M;private int[][] detectTurns0;public static Watch watch = new Watch();public static PCG_XSH_RR rng = new PCG_XSH_RR(System.nanoTime());public static SAState sa = new SAState();private ArrayList<Integer>[][] detectTurns;private int[][] enemy_num;private ArrayList<Enemy> E;private int score;private ArrayList<Move> solution;private int bestScore;private ArrayList<Move> bestSolution;public static void main(String[] args) throws Exception {new Main().run();}private void run() {read();solve();write();}private void write() {for (Move move : solution) {System.out.println(move);}System.out.flush();}private void solve() {detectTurns = new ArrayList[N][N];for (int r = 0; r < N; r++) {for (int c = 0; c < N; c++) {detectTurns[r][c] = new ArrayList<>();}}for (int r = 0; r < N; r++) {for (int c = 0; c < N; c++) {if (map[r][c] == DETECTOR) {for (int d = 0; d < dr.length; d++) {for (int length = 1; length < N; length++) {int nr = r + length * dr[d];int nc = c + length * dc[d];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {break;}if (map[nr][nc] == WALL) {break;}if (map[nr][nc] == DETECTOR) {break;}if (map[nr][nc] == BLOCK) {break;}detectTurns[nr][nc].add(detectTurns0[r][c]);}}}}}points.add(new Point(sr, sc));points.addAll(bfs2(sr, sc));points.add(new Point(gr, gc));points.add(points.size() / 2, new Point(kr, kc));sumDistance = calculataSumDistance();score = (int) -1e9;solution = new ArrayList<>();bestScore = (int) -1e9;bestSolution = new ArrayList<>();multiSA();Utils.debug("solve", "time", watch.getSecondString());}private int calculataSumDistance() {int sumDistance = 0;for (int i = 1; i < points.size(); i++) {sumDistance += manhattanDistance(points.get(i - 1), points.get(i));}return sumDistance;}private void multiSA() {int numRestart = 40;double startTime = watch.getSecond();double endTime = 2.75;double remainTime = endTime - startTime;double startStartTemperature = 1e1;double endStartTemperature = 1e-9;int ok = 0;int ng = 1000;for (double restart = 0; restart < numRestart; restart++) {if (restart % 5 == 0) {ok = 0;ng = 1000;}thresholdDistance = (ok + ng) / 2;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();greedy();solution.clear();for (int j = 1; j < points.size(); j++) {ArrayList<Node> moves = bfs(points.get(j - 1).r, points.get(j - 1).c, solution.size(), points.get(j).r, points.get(j).c);for (int i = 1; i < moves.size(); i++) {solution.add(new Move('M', direction(moves.get(i - 1).r, moves.get(i - 1).c, moves.get(i).r, moves.get(i).c)));}}score = simulate(solution);if (score <= 1) {ng = thresholdDistance;} else {ok = thresholdDistance;}saveBest();}loadBest();Utils.debug("multiSA", sumDistance, "time", watch.getSecondString());}private void greedy() {for (;;) {boolean update = false;for (int i = 1; i < points.size() - 1; i++) {for (int j = i + 1; j < points.size() - 2; j++) {update |= reverse(i, j);}}if (!update) {break;}}}private void saveBest() {if (score > bestScore) {bestScore = score;bestSolution.clear();for (int i = 0; i < solution.size(); i++) {bestSolution.add(solution.get(i));}}}private void loadBest() {score = bestScore;solution.clear();for (int i = 0; i < bestSolution.size(); i++) {solution.add(bestSolution.get(i));}}private void SA() {sa.init();++sa.numIterations;for (;; ++sa.numIterations) {if ((sa.numIterations & ((1 << 5) - 1)) == 0) {sa.update();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("%5d", points.size()), String.format("%5d", sumDistance),String.format("%5d", score), String.format("%5d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());break;}}mutate();}}private void mutate() {double random = 3 * rng.nextDouble();if (random < 1) {remove();} else if (random < 2) {add();} else if (random < 3) {reverse();} else if (random < 4) {swap();} else if (random < 5) {insert();}}private void remove() {if (sumDistance < thresholdDistance) {return;}int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());final Point p = points.get(index1);if (p.r == sr && p.c == sc) {return;}if (p.r == kr && p.c == kc) {return;}if (p.r == gr && p.c == gc) {return;}final int before = manhattanDistance(points.get(index1 - 1), p) + manhattanDistance(p, points.get(index1 + 1));final int after = manhattanDistance(points.get(index1 - 1), points.get(index1 + 1));final int deltaScore = after - before;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;points.remove(index1);removedPoints.add(p);} else {}}private void add() {if (removedPoints.size() == 0) {return;}if (sumDistance > thresholdDistance) {return;}int index1 = (int) (removedPoints.size() * rng.nextDouble());final Point p = removedPoints.get(index1);int index2 = 1 + (int) ((points.size() - 2) * rng.nextDouble());final int before = manhattanDistance(points.get(index2 - 1), points.get(index2));final int after = manhattanDistance(points.get(index2 - 1), p) + manhattanDistance(p, points.get(index2));final int deltaScore = after - before;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;points.add(index2, p);removedPoints.remove(index1);} else {}}private void swap() {if (points.size() <= 3) {return;}int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());int index2 = 1 + (int) ((points.size() - 2 - 1) * rng.nextDouble());if (index2 >= index1) {index2++;}if (index1 > index2) {int swap = index1;index1 = index2;index2 = swap;}if (index1 + 1 == index2) {final Point p1 = points.get(index1 - 1);final Point p2 = points.get(index1);final Point p5 = points.get(index2);final Point p6 = points.get(index2 + 1);final int before = manhattanDistance(p1, p2) + manhattanDistance(p5, p6);final int after = manhattanDistance(p1, p5) + manhattanDistance(p2, p6);final int deltaScore = after - before;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;Collections.swap(points, index1, index2);} else {}} else {final Point p1 = points.get(index1 - 1);final Point p2 = points.get(index1);final Point p3 = points.get(index1 + 1);final Point p4 = points.get(index2 - 1);final Point p5 = points.get(index2);final Point p6 = points.get(index2 + 1);final int before = manhattanDistance(p1, p2) + manhattanDistance(p2, p3);final int before2 = manhattanDistance(p4, p5) + manhattanDistance(p5, p6);final int after = manhattanDistance(p1, p5) + manhattanDistance(p5, p3);final int after2 = manhattanDistance(p4, p2) + manhattanDistance(p2, p6);final int deltaScore = after - before + after2 - before2;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;Collections.swap(points, index1, index2);} else {}}}private void reverse() {if (points.size() <= 3) {return;}int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());int index2 = 1 + (int) ((points.size() - 2 - 1) * rng.nextDouble());if (index2 >= index1) {index2++;}if (index1 > index2) {int swap = index1;index1 = index2;index2 = swap;}final Point p1 = points.get(index1 - 1);final Point p2 = points.get(index1);final Point p5 = points.get(index2);final Point p6 = points.get(index2 + 1);final int before = manhattanDistance(p1, p2) + manhattanDistance(p5, p6);final int after = manhattanDistance(p1, p5) + manhattanDistance(p2, p6);final int deltaScore = after - before;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;for (int l = index1, r = index2; l < r; l++, r--) {Collections.swap(points, l, r);}} else {}}private boolean reverse(int i, int j) {if (points.size() <= 3) {return false;}int index1 = i;int index2 = j;if (index2 >= index1) {index2++;}if (index1 > index2) {int swap = index1;index1 = index2;index2 = swap;}final Point p1 = points.get(index1 - 1);final Point p2 = points.get(index1);final Point p5 = points.get(index2);final Point p6 = points.get(index2 + 1);final int before = manhattanDistance(p1, p2) + manhattanDistance(p5, p6);final int after = manhattanDistance(p1, p5) + manhattanDistance(p2, p6);final int deltaScore = after - before;if (deltaScore < -1e-9) {sumDistance += deltaScore;for (int l = index1, r = index2; l < r; l++, r--) {Collections.swap(points, l, r);}return true;} else {}return false;}private void insert() {if (points.size() <= 3) {return;}int index1 = 1 + (int) ((points.size() - 2) * rng.nextDouble());final Point p1 = points.get(index1 - 1);final Point p2 = points.get(index1);final Point p3 = points.get(index1 + 1);final int before = manhattanDistance(p1, p2) + manhattanDistance(p2, p3);final int after = manhattanDistance(p1, p3);points.remove(index1);int index2 = 1 + (int) ((points.size() - 2 - 0) * rng.nextDouble());final Point p4 = points.get(index2 - 1);final Point p5 = points.get(index2);final int before2 = manhattanDistance(p4, p5);final int after2 = manhattanDistance(p4, p2) + manhattanDistance(p2, p5);final int deltaScore = after - before + after2 - before2;if (sa.acceptS(deltaScore)) {sumDistance += deltaScore;points.add(index2, p2);} else {points.add(index1, p2);}}private char direction(int r, int c, int r2, int c2) {if (r2 - r < 0) {return dir[0];}if (r2 - r > 0) {return dir[1];}if (c2 - c < 0) {return dir[2];}if (c2 - c > 0) {return dir[3];}throw new AssertionError();}private ArrayList<Node> bfs(int sr, int sc, int turn, int gr, int gc) {boolean[][] used = new boolean[N][N];PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.damage, o2.damage));{used[sr][sc] = true;queue.add(new Node(null, sr, sc, turn, 0));}for (; !queue.isEmpty();) {Node node = queue.poll();if (node.r == gr && node.c == gc) {return reverse2(toList(node));}for (int d = 0; d < dr.length; d++) {int nr = node.r + dr[d];int nc = node.c + dc[d];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {continue;}if (map[nr][nc] == WALL) {continue;}if (map[nr][nc] == BLOCK) {continue;}if (map[nr][nc] == DETECTOR) {continue;}if (used[nr][nc]) {continue;}used[nr][nc] = true;int ndamage = node.damage + 1;for (Integer turn2 : detectTurns[nr][nc]) {if ((node.turn + 1) % turn2 == 0) {ndamage += D;}}queue.add(new Node(node, nr, nc, node.turn + 1, ndamage));}}throw new AssertionError();}private ArrayList<Point> bfs2(int sr, int sc) {ArrayList<Point> jewels = new ArrayList<>();boolean[][] used = new boolean[N][N];LinkedList<Node> queue = new LinkedList<>();{used[sr][sc] = true;queue.add(new Node(null, sr, sc));}for (; !queue.isEmpty();) {Node node = queue.poll();if (map[node.r][node.c] == JEWEL) {jewels.add(new Point(node.r, node.c));}for (int d = 0; d < dr.length; d++) {int nr = node.r + dr[d];int nc = node.c + dc[d];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {continue;}if (map[nr][nc] == WALL) {continue;}if (map[nr][nc] == BLOCK) {continue;}if (map[nr][nc] == DETECTOR) {continue;}if (used[nr][nc]) {continue;}used[nr][nc] = true;queue.add(new Node(node, nr, nc));}}return jewels;}private void read() {try (Scanner in = new Scanner(System.in)) {N = in.nextInt();watch.init();D = in.nextInt();Utils.debug("D", D);H = in.nextInt();map = new int[N][N];int M2 = 0;for (int r = 0; r < N; r++) {String line = in.next();for (int c = 0; c < N; c++) {if (line.charAt(c) == '.') {map[r][c] = EMPTY;} else if (line.charAt(c) == '#') {map[r][c] = WALL;} else if (line.charAt(c) == 'S') {sr = r;sc = c;} else if (line.charAt(c) == 'G') {gr = r;gc = c;} else if (line.charAt(c) == 'K') {kr = r;kc = c;} else if (line.charAt(c) == 'J') {map[r][c] = JEWEL;} else if (line.charAt(c) == 'F') {map[r][c] = GUNPOWDER;} else if (line.charAt(c) == 'E') {map[r][c] = DETECTOR;M2++;}}}M = in.nextInt();detectTurns0 = new int[N][N];enemy_num = new int[N][N];E = new ArrayList<>();for (int i = 0; i < M; i++) {int y = in.nextInt();int x = in.nextInt();int d = in.nextInt();detectTurns0[y][x] = d;enemy_num[y][x] = i;E.add(new Enemy(y, x, d));}} catch (Exception e) {e.printStackTrace();}}private <T> ArrayList<T> reverse2(ArrayList<T> list) {for (int l = 0, r = list.size() - 1; l < r; l++, r--) {list.set(r, list.set(l, list.get(r)));}return list;}private ArrayList<Node> toList(Node state0) {ArrayList<Node> res = new ArrayList<>();for (Node current = state0; current != null; current = current.parent) {res.add(current);}return res;}private ArrayList<Node> toList0(Node state0) {ArrayList<Node> res = new ArrayList<>();for (Node current = state0; current.parent != null; current = current.parent) {res.add(current);}return res;}private static int manhattanDistance(Point p, Point q) {return manhattanDistance(p.r, p.c, q.r, q.c);}private static int manhattanDistance(int r, int c, int r2, int c2) {return Math.abs(r - r2) + Math.abs(c - c2);}private int direction(char c) {int d = -1;for (int i = 0; i < 4; i++) {if (c == dir[i])d = i;}return d;}private boolean range_out(int y, int x) {if (y < 0 || y >= grid_size)return true;if (x < 0 || x >= grid_size)return true;return false;}private int simulate(ArrayList<Move> solution) {int now_y = sr;int now_x = sc;boolean get_key = false;int fire_left = 0;int damage = 0;int score = 0;int jewel_value = 10;int turn = 0;int[][] map = new int[N][N];for (int r = 0; r < N; r++) {for (int c = 0; c < N; c++) {map[r][c] = this.map[r][c];}}for (int i = 0; i < solution.size(); i++) {char c = solution.get(i).a;if (c == 'S') {} else {char d = solution.get(i).b;int dir = direction(d);if (dir == -1) {return 1;}if (c == 'M') {now_y += dy[dir];now_x += dx[dir];if (range_out(now_y, now_x)) {return 1;}int cell = map[now_y][now_x];if (cell == WALL) {return 1;} else if (cell == BLOCK) {return 1;} else if (cell == DETECTOR) {return 1;} else if (now_y == kr && now_x == kc) {get_key = true;map[now_y][now_x] = EMPTY;} else if (cell == GUNPOWDER) {fire_left++;map[now_y][now_x] = EMPTY;} else if (cell == JEWEL) {score += jewel_value;map[now_y][now_x] = EMPTY;} else if (now_y == gr && now_x == gc) {if (get_key) {return score;}}} else if (c == 'B') {int ny = now_y + dy[dir];int nx = now_x + dx[dir];if (range_out(ny, nx)) {return 1;}if (map[ny][nx] != EMPTY && map[ny][nx] != BLOCK) {return 1;}if (map[ny][nx] == EMPTY) {map[ny][nx] = BLOCK;} else {map[ny][nx] = EMPTY;}} else if (c == 'F') {if (fire_left <= 0) {return 1;}fire_left--;int ny = now_y + dy[dir];int nx = now_x + dx[dir];while (!range_out(ny, nx)) {if (map[ny][nx] == WALL || map[ny][nx] == BLOCK) {break;} else if (map[ny][nx] == DETECTOR) {map[ny][nx] = EMPTY;int num = enemy_num[ny][nx];E.get(num).destroyed = true;break;}ny += dy[dir];nx += dx[dir];}} else {return 1;}}for (int k = 0; k < 4; k++) {int ny = now_y + dy[k];int nx = now_x + dx[k];while (!range_out(ny, nx)) {int cell = map[ny][nx];if (cell == WALL || cell == BLOCK) {break;} else if (cell == DETECTOR) {int num = enemy_num[ny][nx];int d2 = E.get(num).d;if (turn % d2 == 0) {damage += D;}break;}ny += dy[k];nx += dx[k];}}damage++;if (damage >= H) {Utils.debug("turn", turn, "damage", damage);return 1;}turn++;}return 1;}}class Point {int r;int c;Point(int r, int c) {this.r = r;this.c = c;}}class SAState {public 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 ? Main.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() {range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);}public void updateTime() {time = useTime ? Main.watch.getSecond() : numIterations;}public boolean isTLE() {return time >= endTime;}public boolean accept(double deltaScore) {return acceptB(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[Main.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[Main.rng.nextInt() & 32767] < d) {acceptIterations++;lastAcceptTemperature = inverseTemperature;return true;}return false;}}final class Utils {private Utils() {}public static final void debug(Object... 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));}}}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;}}class Node {Node parent;int r;int c;int turn;int damage;Node(Node parent, int r, int c) {this.parent = parent;this.r = r;this.c = c;}Node(Node parent, int r, int c, int turn, int damage) {this.parent = parent;this.r = r;this.c = c;this.turn = turn;this.damage = damage;}}class Move {char a;char b;Move(char a, char b) {this.a = a;this.b = b;}@Overridepublic String toString() {return a + " " + b;}}class Enemy {public boolean destroyed;int y, x, d;Enemy(int y, int x, int d) {this.y = y;this.x = x;this.d = d;this.destroyed = false;}}