結果

問題 No.5019 Hakai Project
ユーザー EvbCFfp1XBEvbCFfp1XB
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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), new
            Region(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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0