結果
| 問題 |
No.5015 Escape from Labyrinth
|
| コンテスト | |
| ユーザー |
 Yu_212
|
| 提出日時 | 2023-04-16 15:13:37 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 19,476 bytes |
| コンパイル時間 | 3,262 ms |
| コンパイル使用メモリ | 101,516 KB |
| 実行使用メモリ | 71,400 KB |
| スコア | 95,980 |
| 最終ジャッジ日時 | 2023-04-16 15:15:15 |
| 合計ジャッジ時間 | 85,906 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 94 WA * 6 |
ソースコード
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};
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;
}
// debug(p, bi, bd, dsum);
if (dsum + bd * mul[D] >= 60 * 750) {
break;
}
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 > 1500) {
debug("!");
}
// 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);
debug(totalCost);
return 0;
}
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;
}
}
}