結果
問題 | No.5019 Hakai Project |
ユーザー | EvbCFfp1XB |
提出日時 | 2023-11-19 18:41:52 |
言語 | Java21 (openjdk 21) |
結果 |
TLE
|
実行時間 | - |
コード長 | 22,448 bytes |
コンパイル時間 | 2,911 ms |
コンパイル使用メモリ | 92,244 KB |
実行使用メモリ | 69,416 KB |
スコア | 1,744,524,770 |
最終ジャッジ日時 | 2023-11-19 18:44:35 |
合計ジャッジ時間 | 159,704 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2,938 ms
64,572 KB |
testcase_01 | AC | 2,951 ms
66,748 KB |
testcase_02 | AC | 2,965 ms
65,252 KB |
testcase_03 | TLE | - |
testcase_04 | AC | 2,962 ms
65,280 KB |
testcase_05 | AC | 2,935 ms
64,616 KB |
testcase_06 | AC | 2,943 ms
64,560 KB |
testcase_07 | AC | 2,949 ms
66,828 KB |
testcase_08 | TLE | - |
testcase_09 | AC | 2,938 ms
65,260 KB |
testcase_10 | AC | 2,961 ms
65,504 KB |
testcase_11 | AC | 2,951 ms
66,796 KB |
testcase_12 | AC | 2,950 ms
64,764 KB |
testcase_13 | AC | 2,947 ms
65,248 KB |
testcase_14 | AC | 2,967 ms
66,476 KB |
testcase_15 | AC | 2,944 ms
66,736 KB |
testcase_16 | AC | 2,946 ms
64,756 KB |
testcase_17 | AC | 2,938 ms
64,436 KB |
testcase_18 | AC | 2,943 ms
66,748 KB |
testcase_19 | AC | 2,935 ms
69,224 KB |
testcase_20 | AC | 2,949 ms
65,288 KB |
testcase_21 | AC | 2,953 ms
66,732 KB |
testcase_22 | AC | 2,954 ms
65,288 KB |
testcase_23 | AC | 2,934 ms
64,428 KB |
testcase_24 | AC | 2,947 ms
65,248 KB |
testcase_25 | AC | 2,962 ms
64,616 KB |
testcase_26 | AC | 2,948 ms
65,432 KB |
testcase_27 | AC | 2,949 ms
66,396 KB |
testcase_28 | TLE | - |
testcase_29 | AC | 2,946 ms
66,480 KB |
testcase_30 | AC | 2,936 ms
66,592 KB |
testcase_31 | AC | 2,937 ms
64,520 KB |
testcase_32 | AC | 2,943 ms
65,180 KB |
testcase_33 | AC | 2,947 ms
65,320 KB |
testcase_34 | AC | 2,956 ms
64,760 KB |
testcase_35 | AC | 2,957 ms
69,416 KB |
testcase_36 | AC | 2,953 ms
66,788 KB |
testcase_37 | AC | 2,951 ms
65,344 KB |
testcase_38 | AC | 2,952 ms
66,748 KB |
testcase_39 | AC | 2,957 ms
64,624 KB |
testcase_40 | AC | 2,969 ms
66,656 KB |
testcase_41 | AC | 2,947 ms
65,296 KB |
testcase_42 | TLE | - |
testcase_43 | AC | 2,938 ms
64,520 KB |
testcase_44 | AC | 2,937 ms
64,804 KB |
testcase_45 | AC | 2,946 ms
64,676 KB |
testcase_46 | AC | 2,948 ms
65,388 KB |
testcase_47 | AC | 2,987 ms
66,828 KB |
testcase_48 | AC | 2,940 ms
66,464 KB |
testcase_49 | AC | 2,932 ms
67,032 KB |
ソースコード
import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Scanner;public class Main {private static final int EMPTY = 0;private static final int BUILDING = 1;private static final int SHOP = 2;private static final int margin = 9;private static final int shift = 0;private int N;private int M;private int[][] map;private int[] cost;private int[][] dy;private int[][] dx;static Watch watch = new Watch();static PCG_XSH_RR rng = new PCG_XSH_RR(114514L);private SAState sa = new SAState();private int score;private int[][] cover;private ArrayList<BombPoint>[] points = new ArrayList[4];private Region[] regions;private ArrayList<BombPoint>[] shops = new ArrayList[4];public static void main(String[] args) throws Exception {new Main().run();}private void run() {read();regions = new Region[] { new Region(0, N / 2, 0, N / 2, 0 + margin - shift, N / 2 - margin - shift, 0 + margin - shift, N / 2 - margin -shift), new Region(0, N / 2, N / 2, N, 0 + margin - shift, N / 2 - margin - shift, N / 2 + margin + shift, N - margin + shift), newRegion(N / 2, N, N / 2, N, N / 2 + margin + shift, N - margin + shift, N / 2 + margin + shift, N - margin + shift), new Region(N / 2, N,0, N / 2, N / 2 + margin + shift, N - margin + shift, 0 + margin - shift, N / 2 - margin - shift), };for (int i = 0; i < points.length; i++) {points[i] = new ArrayList<>();}for (int i = 0; i < shops.length; i++) {shops[i] = new ArrayList<>();}for (int regioni = 0; regioni < points.length; regioni++) {Region region = regions[regioni];for (int r = region.minR; r < region.maxR; r++) {for (int c = region.minC; c < region.maxC; c++) {if (map[r][c] == SHOP) {shops[regioni].add(new BombPoint(r, c, -1));}}}}for (int regioni = 0; regioni < points.length; regioni++) {Utils.debug("regioni", regioni);Region region = regions[regioni];Point nearestShop = null;for (int r = 0; r < N; r++) {for (int c = 0; c < N; c++) {if (cover[r][c] == 0 && map[r][c] == SHOP) {if (nearestShop == null || euclideanDistance(r, c, (region.minR2 + region.maxR2) / 2, (region.minC2 + region.maxC2) / 2) <euclideanDistance(nearestShop.r, nearestShop.c, (region.minR2 + region.maxR2) / 2, (region.minC2 + region.maxC2) / 2)) {nearestShop = new Point(r, c);}}}}points[regioni].add(new BombPoint(nearestShop.r, nearestShop.c, -1));setCoverGreedy(region, regioni);}score = calculateScore();Utils.debug("score", score);multiSA();ArrayList<Move> moves = new ArrayList<>();Point halc = new Point(0, 0);for (int i = 0; i < points.length; i++) {ArrayList<BombPoint> ps = points[i];for (int j = 0; j < ps.size(); j++) {BombPoint p = ps.get(j);if (j == 0) {move(p.r, p.c, moves, halc);for (int k = 1; k < ps.size(); k++) {moves.add(new Move(2, "" + (1 + ps.get(k).bomb)));}} else {move(p.r, p.c, moves, halc);moves.add(new Move(3, "" + (1 + p.bomb)));}}}System.out.println(moves.size());for (Move move : moves) {System.out.println(move.type + " " + move.s);}System.out.flush();}int[][] cover2;private int calculateScore() {if (cover2 == null) {cover2 = new int[N][N];}for (int r = 0; r < N; r++) {for (int c = 0; c < N; c++) {cover2[r][c] = 0;}}int score = 0;int r = 0;int c = 0;for (int i = 0; i < points.length; i++) {ArrayList<BombPoint> ps = points[i];for (int j = 0; j < ps.size(); j++) {BombPoint p = ps.get(j);if (j == 0) {score += 2 * manhattanDistance(r, c, p.r, p.c) * 1 * 1;if (cover2[p.r][p.c] != 0) {score += 1e9;}for (int k = 1; k < ps.size(); k++) {score += cost[ps.get(k).bomb];}} else {score += 2 * manhattanDistance(r, c, p.r, p.c) * (1 + ps.size() - j) * (1 + ps.size() - j);updateCover2(cover2, p.r, p.c, p.bomb, 1);}r = p.r;c = p.c;}}return score;}private static void move(int r, int c, ArrayList<Move> moves, Point halc) {while (halc.r != r) {if (halc.r < r) {moves.add(new Move(1, "D"));halc.r++;} else {moves.add(new Move(1, "U"));halc.r--;}}while (halc.c != c) {if (halc.c < c) {moves.add(new Move(1, "R"));halc.c++;} else {moves.add(new Move(1, "L"));halc.c--;}}}private static final int manhattanDistance(int r1, int c1, int r2, int c2) {int deltaR = r2 - r1;int deltaC = c2 - c1;return Math.abs(deltaR) + Math.abs(deltaC);}private static final double euclideanDistance(int r1, int c1, int r2, int c2) {int deltaR = r2 - r1;int deltaC = c2 - c1;return Math.sqrt(deltaR * deltaR + deltaC * deltaC);}private void setCoverGreedy(Region region, int index) {while (!isCoverd(cover, region)) {double max = 0;int maxBomb = -1;int maxR = -1;int maxC = -1;for (int r2 = region.minR2; r2 < region.maxR2; r2++) {for (int c2 = region.minC2; c2 < region.maxC2; c2++) {for (int bomb = 0; bomb < M; bomb++) {int count = 0;for (int i = 0; i < dy[bomb].length; i++) {int nr = r2 + dy[bomb][i];int nc = c2 + dx[bomb][i];if (!Utils.isValid(nr, region.minR, region.maxR) || !Utils.isValid(nc, region.minC, region.maxC)) {continue;}if (cover[nr][nc] != 0) {continue;}count++;}if (count > max) {max = count;maxBomb = bomb;maxR = r2;maxC = c2;}}}}points[index].add(new BombPoint(maxR, maxC, maxBomb));updateCover(maxR, maxC, maxBomb, 1);}}private void setCoverGreedy2(int index0) {Region region = regions[index0];while (!isCoverd(cover)) {double max = 0;int maxBomb = -1;int maxR = -1;int maxC = -1;int r2 = (int) (region.minR2 + (region.maxR2 - region.minR2) * rng.nextDouble());{int c2 = (int) (region.minC2 + (region.maxC2 - region.minC2) * rng.nextDouble());{int bomb = rng.nextInt(M);{int count = 0;for (int i = 0; i < dy[bomb].length; i++) {int nr = r2 + dy[bomb][i];int nc = c2 + dx[bomb][i];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {continue;}if (cover[nr][nc] != 0) {continue;}count++;}if (count > max) {max = count;maxBomb = bomb;maxR = r2;maxC = c2;}}}}if (maxBomb == -1) {continue;}points[index0].add(new BombPoint(maxR, maxC, maxBomb));updateCover(maxR, maxC, maxBomb, 1);}}private void updateCover(int r, int c, int bomb, int value) {if (bomb < 0) {return;}for (int i = 0; i < dy[bomb].length; i++) {int nr = r + dy[bomb][i];int nc = c + dx[bomb][i];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {continue;}cover[nr][nc] += value;}}private void updateCover2(int[][] cover, int r, int c, int bomb, int value) {if (bomb < 0) {return;}for (int i = 0; i < dy[bomb].length; i++) {int nr = r + dy[bomb][i];int nc = c + dx[bomb][i];if (!Utils.isValid(nr, 0, N) || !Utils.isValid(nc, 0, N)) {continue;}cover[nr][nc] += value;}}private void multiSA() {int numRestart = 1;double startTime = watch.getSecond();double endTime = 2.75;double remainTime = endTime - startTime;double startStartTemperature = 1e2;double endStartTemperature = 1e-9;for (double restart = 0; restart < numRestart; restart++) {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();}Utils.debug("multiSA", "score", score, "time", watch.getSecondString());}private void SA() {final double deltaSecond = (sa.endTime - sa.startTime) * 0.999 / 10;double thresholdSecond = sa.startTime + deltaSecond;sa.init();for (;; ++sa.numIterations) {if ((sa.numIterations & ((1 << 5) - 1)) == 0) {sa.update();if (sa.time > thresholdSecond) {thresholdSecond += deltaSecond;Utils.debug(sa.numIterations, String.format("%6.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%6.2f%%",100.0 * sa.acceptIterations / sa.validIterations), String.format("%5d", score), String.format("%8.6f", 1.0 / sa.inverseTemperature), String.format("%8.6f", 1.0 / sa.lastAcceptTemperature), sa.time);}if (sa.isTLE()) {break;}}mutate();}}private void mutate() {double random = 3 * rng.nextDouble();if (random < 1) {swap();} else if (random < 2) {add();} else if (random < 3) {shop();}}private void add() {int index = rng.nextInt(points.length);ArrayList<BombPoint> ps = points[index];ArrayList<BombPoint> copy = new ArrayList<>();for (int i = 0; i < ps.size(); i++) {copy.add(ps.get(i));}int random = 1 + rng.nextInt(2);for (int i = 0; i < random; i++) {if (ps.size() <= 1) {continue;}int index2 = 1 + rng.nextInt(ps.size() - 1);BombPoint removed = ps.remove(index2);updateCover(removed.r, removed.c, removed.bomb, -1);}setCoverGreedy2(index);int deltaScore = calculateScore() - score;if (sa.accept(deltaScore)) {score += deltaScore;} else {for (int i = ps.size() - 1; i >= 0; i--) {BombPoint removed = ps.remove(i);updateCover(removed.r, removed.c, removed.bomb, -1);}for (int i = 0; i < copy.size(); i++) {BombPoint bombPoint = copy.get(i);ps.add(bombPoint);updateCover(bombPoint.r, bombPoint.c, bombPoint.bomb, 1);}}}private void swap() {int index = rng.nextInt(points.length);if (points[index].size() <= 2) {return;}int index1 = 1 + rng.nextInt(points[index].size() - 1);int index2 = 1 + rng.nextInt(points[index].size() - 1);if (index1 == index2) {return;}Collections.swap(points[index], index1, index2);int deltaScore = calculateScore() - score;if (sa.accept(deltaScore)) {score += deltaScore;} else {Collections.swap(points[index], index1, index2);}}private void shop() {int index = rng.nextInt(points.length);BombPoint current = points[index].get(0);BombPoint shop = shops[index].get(rng.nextInt(shops[index].size()));points[index].set(0, shop);int deltaScore = calculateScore() - score;if (sa.accept(deltaScore)) {score += deltaScore;} else {points[index].set(0, current);}}private static boolean isCoverd(int[][] cover2, Region region) {return isCoverd(cover2, region.minR, region.maxR, region.minC, region.maxC);}private boolean isCoverd(int[][] cover2) {return isCoverd(cover2, 0, N, 0, N);}private static boolean isCoverd(int[][] cover2, int minR, int maxR, int minC, int maxC) {for (int r = minR; r < maxR; r++) {for (int c = minC; c < maxC; c++) {if (cover2[r][c] <= 0) {return false;}}}return true;}private void read() {try (final Scanner in = new Scanner(System.in)) {N = in.nextInt();watch.init();M = in.nextInt();map = new int[N][N];for (int r = 0; r < N; r++) {String line = in.next();for (int c = 0; c < N; c++) {char ch = line.charAt(c);map[r][c] = ch == '.' ? EMPTY : ch == '#' ? BUILDING : SHOP;}}cost = new int[M];dy = new int[M][];dx = new int[M][];for (int i = 0; i < M; i++) {cost[i] = in.nextInt();int l = in.nextInt();int[] dy2 = new int[l];int[] dx2 = new int[l];for (int j = 0; j < l; j++) {dy2[j] = in.nextInt();dx2[j] = in.nextInt();}dy[i] = dy2;dx[i] = dx2;}} catch (Exception e) {e.printStackTrace();}cover = new int[N][N];}}class Utils {private Utils() {}public static final void debug(Object... o) {System.err.println(toString(o));System.err.flush();}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 SAState {public static final 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();}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 acceptS(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;}}class Point {int r;int c;public Point(int r, int c) {super();this.r = r;this.c = c;}}class BombPoint {int r;int c;int bomb;public BombPoint(int r, int c, int bomb) {super();this.r = r;this.c = c;this.bomb = bomb;}}class Move {int type;String s;public Move(int type, String s) {super();this.type = type;this.s = s;}}class Region {int minR;int maxR;int minC;int maxC;int minR2;int maxR2;int minC2;int maxC2;public Region(int minR, int maxR, int minC, int maxC, int minR2, int maxR2, int minC2, int maxC2) {super();this.minR = minR;this.maxR = maxR;this.minC = minC;this.maxC = maxC;this.minR2 = minR2;this.maxR2 = maxR2;this.minC2 = minC2;this.maxC2 = maxC2;}public Region(int minR, int maxR, int minC, int maxC) {super();this.minR = minR;this.maxR = maxR;this.minC = minC;this.maxC = maxC;}}