結果
| 問題 |
No.5007 Steiner Space Travel
|
| コンテスト | |
| ユーザー |
 Yu_212
|
| 提出日時 | 2022-07-30 17:10:11 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 915 ms / 1,000 ms |
| コード長 | 21,030 bytes |
| コンパイル時間 | 3,308 ms |
| 実行使用メモリ | 78,100 KB |
| スコア | 8,865,437 |
| 最終ジャッジ日時 | 2022-07-30 17:10:44 |
| 合計ジャッジ時間 | 29,618 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
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;
import java.util.stream.IntStream;
public class Main {
boolean isLocal;
Random rand = new Random();
In in = new In(System.in);
PrintStream out = System.out;
long inf = 0x1fffffffffffffffL;
int iinf = 0x3fffffff;
long startTime;
private static final int s = 1001;
private static final int n = 100;
private static final int m = 8;
Pos[] planets = new Pos[n];
boolean[] grid = new boolean[s * s];
int[][] dist = new int[n][n];
int[][] neighbor = new int[n][n - 1];
class St {
private final Pos p;
private final int upd;
St(Pos p, int upd) {
this.p = p;
this.upd = upd;
}
}
long solve(int seed) {
startTime = System.currentTimeMillis();
in();
State state = initialState();
while (!elapsed(400)) {
state.optimize();
}
debug(state.ds);
List<St> cand = new ArrayList<>();
for (int i = 0; i < 15000; i++) {
Pos p = pos(rand.next(s), rand.next(s));
int upd = state.station(0, p, false);
// debug(p, upd);
if (upd > -350000) {
continue;
}
cand.add(new St(p, upd));
}
debug(cand.size());
int[] last = new int[m];
for (St st : cand) {
int best = 0;
int bi = -1;
for (int i = 0; i < m; i++) {
int upd = state.station(i, st.p, false);
if (best > upd) {
best = upd;
bi = i;
}
}
// debug(bi, st.p, st.upd, best, iii++);
if (bi != -1) {
state.station(bi, st.p, true);
last[bi] = st.upd;
}
}
state.optAll();
debug(last);
debug(state.ds);
answer(state);
return isLocal ? Math.round(1000000000.0 / (Math.sqrt(state.ds) + 1000)) : 0;
}
void in() {
Pos.init(1001, 1001);
in.nextInt();
in.nextInt();
for (int i = 0; i < n; i++) {
int a = in.nextInt();
int b = in.nextInt();
planets[i] = pos(a, b);
grid[planets[i].z] = true;
}
IntStream.range(0, n).forEach(i -> {
Integer[] a = new Integer[n - 1];
Arrays.setAll(dist[i], j -> planets[i].dist(planets[j]) * 25);
Arrays.setAll(a, j -> j < i ? j : j + 1);
Arrays.sort(a, Comparator.comparingLong(j -> dist[i][j]));
Arrays.setAll(neighbor[i], j -> a[j]);
});
}
class State {
double score;
boolean hasScore;
State prevCopy;
int ds;
int[] tour;
int[] position;
Pos[] station;
int[] relay;
int[] relay2;
State(int[] tour, int[] position, int ds, int[] relay, int[] relay2, Pos[] station) {
this.tour = tour;
this.position = position;
this.ds = ds;
this.station = station;
this.relay = relay;
this.relay2 = relay2;
}
State(State prev) {
this.score = prev.score;
this.hasScore = true;
}
State rollback() {
return prevCopy;
}
int neighbor0(double stage) {
return 0;
}
int neighbor(double stage) {
hasScore = false;
prevCopy = copy();
return neighbor0(stage);
}
State copy() {
return new State(this);
}
boolean tryTwoOpt() {
boolean updated = false;
for (int i = 0; i < n; i++) {
int a = tour[i];
int b = tour[i + 1 < n ? i + 1 : 0];
for (int k = 0; k < n - 1; k++) {
int j = position[neighbor[a][k]];
int c = tour[j];
int d = tour[j + 1 < n ? j + 1 : 0];
if (a == d || b == c) {
continue;
}
if (dist[a][c] > dist[a][b]) {
break;
}
long before = dist[a][b] + dist[c][d];
long after = dist[a][c] + dist[b][d];
if (after < before) {
twoOpt(i, j);
updated = true;
break;
}
}
}
return updated;
}
void twoOpt(int i, int j) {
if (i > j) {
int temp = i;
i = j;
j = temp;
}
while (i + 1 < j) {
i++;
int temp = tour[i];
tour[i] = tour[j];
tour[j] = temp;
position[tour[i]] = i;
position[tour[j]] = j;
j--;
}
}
void doubleBridge() {
int[] i = new int[4];
do {
Arrays.setAll(i, j -> rand.next(n));
Arrays.sort(i);
} while (!(i[0] + 1 < i[1] && i[1] + 1 < i[2] && i[2] + 1 < i[3] && (0 < i[0] || i[3] < n - 1)));
int a = i[1] - i[0];
int b = i[2] - i[1];
int c = i[3] - i[2];
int[] copy = Arrays.copyOfRange(tour, i[0] + 1, i[3] + 1);
int k = i[0] + 1;
for (int j = 0; j < c; j++) {
tour[k + j] = copy[a + b + j];
position[copy[a + b + j]] = k + j;
}
k += c;
for (int j = 0; j < b; j++) {
tour[k + j] = copy[a + j];
position[copy[a + j]] = k + j;
}
k += b;
for (int j = 0; j < a; j++) {
tour[k + j] = copy[j];
position[copy[j]] = k + j;
}
}
void optimize() {
int[] oldTour = tour.clone();
int[] oldPosition = position.clone();
doubleBridge();
while (tryTwoOpt());
int nds = calcDist();
if (ds > nds) {
ds = nds;
} else {
tour = oldTour;
position = oldPosition;
}
}
int station(int k, Pos p, boolean change) {
Pos old = station[k];
station[k] = p;
int ods = ds;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += optRelay(i, change);
}
if (change) {
ds = sum;
} else {
station[k] = old;
}
return sum - ods;
}
int optRelay(int i, boolean change) {
int j = i == n - 1 ? 0 : i + 1;
if (change) relay[i] = -1;
int min = dist[tour[i]][tour[j]];
for (int k = 0; k < m; k++) {
int upd = dist(tour[i], station[k], tour[j]);
if (min > upd) {
min = upd;
if (change) relay[i] = n + k;
}
}
return min;
}
int optRelay2(int i) {
int j = i == n - 1 ? 0 : i + 1;
int min = relay[i] == -1 ? dist[tour[i]][tour[j]] : dist(tour[i], station[relay[i] - n], tour[j]);
for (int k = 0; k < m; k++) {
for (int l = 0; l < m; l++) {
if (k == l) {
continue;
}
int upd = dist(tour[i], station[k], station[l], tour[j]);
if (min > upd) {
min = upd;
debug("?", i, k, l);
relay[i] = n + k;
relay2[i] = n + l;
}
}
}
return min;
}
void optAll() {
int ods = ds;
for (int k = 0; k < m; k++) {
int sx = 0;
int sy = 0;
int ss = 0;
for (int i = 0; i < n; i++) {
int j = i == n - 1 ? 0 : i + 1;
if (relay[i] == k + n) {
Pos pi = planets[tour[i]];
Pos pj = planets[tour[j]];
sx += pi.x + pj.x;
sy += pi.y + pj.y;
ss += 2;
}
}
station(k, pos(Math.round((float)sx / ss), Math.round((float)sy / ss)), true);
}
debug("!", ds - ods);
int sum = 0;
for (int i = 0; i < n; i++) {
sum += optRelay2(i);
}
debug("!!", sum - ds);
ds = sum;
// for (int i = 0; i < n; i++) {
// int j = i == n - 1 ? 0 : i + 1;
// int min = dist[tour[i]][tour[j]];
// for (int k = 0; k < m; k++) {
// int upd = dist(tour[i], station[k], tour[j]);
// if (min > upd) {
// min = upd;
// relay[i] = n + k;
// }
// }
// for (int k = 0; k < n; k++) {
// int upd = dist(tour[i], planets[k], tour[j]) * 5;
// if (min > upd) {
// debug("!" + k + ", " + (min - upd));
// min = upd;
// relay[i] = k;
// }
// }
// }
}
int dist(int i, Pos r, int j) {
if (r == null) {
return dist[i][j];
} else {
return (planets[i].dist(r) + r.dist(planets[j])) * 5;
}
}
int dist(int i, Pos r1, Pos r2, int j) {
return planets[i].dist(r1) * 5 + r1.dist(r2) + r2.dist(planets[j]) * 5;
}
int calcDist() {
int ds = 0;
for (int i = 0; i < n; i++) {
int j = i == n - 1 ? 0 : i + 1;
ds += dist[tour[i]][tour[j]];
}
return ds;
}
double getScore() {
if (!hasScore) {
score = calcScore();
hasScore = true;
}
return score;
}
double calcScore() {
double score = 0;
return score;
}
long realScore() {
int score = 0;
return score;
}
}
State initialState() {
int[] tour = new int[n];
int[] position = new int[n];
BitSet used = new BitSet(n);
used.set(0);
int ds = 0;
int prev = 0;
for (int i = 1; i < n; i++) {
for (int k = 0; k < n - 1; k++) {
int j = neighbor[prev][k];
if (!used.get(j)) {
ds += dist[prev][j];
prev = j;
tour[i] = j;
position[j] = i;
used.set(j);
break;
}
}
}
Pos[] station = new Pos[m];
int[] relay = new int[n];
int[] relay2 = new int[n];
Arrays.fill(relay, -1);
Arrays.fill(relay2, -1);
return new State(tour, position, ds, relay, relay2, station);
}
void answer(State state) {
for (Pos pos : state.station) {
if (pos == null) {
out.println("0 0");
} else {
out.println(pos.x + " " + pos.y);
}
}
int k = n + 1;
for (int i = 0; i < n; i++) {
if (state.relay[i] != -1) {
k++;
}
if (state.relay2[i] != -1) {
k++;
}
}
out.println(k);
for (int i = 0; i < n; i++) {
out.println("1 " + (state.tour[i] + 1));
if (state.relay[i] != -1) {
if (state.relay[i] < n) {
out.println("1 " + (state.relay[i] + 1));
} else {
out.println("2 " + (state.relay[i] - n + 1));
}
if (state.relay2[i] != -1) {
out.println("2 " + (state.relay2[i] - n + 1));
}
}
}
out.println("1 1");
}
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(" ")));
}
Pos pos(int x, int y) {
return Pos.instances[y * s + x];
}
Pos pos(int z) {
return Pos.instances[z];
}
static class Pos implements Comparable<Pos> {
static Pos[] instances;
static void init(int h, int w) {
instances = new Pos[h * w];
for (int i = 0; i < h * w; i++) {
instances[i] = new Pos(i % w, i / w, i);
}
}
final int x, y, z;
private Pos(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
int dist(Pos o) {
int xd = (x - o.x);
int yd = (y - o.y);
return xd * xd + yd * yd;
}
@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);
}
}
State climbing(State state, long timeLimit) {
timeLimit *= 1000000;
long startTime = System.nanoTime();
State bestState = state.copy();
double bestScore = state.getScore();
while (true) {
long nowTime = System.nanoTime() - startTime;
if (nowTime >= timeLimit) {
break;
}
double prevScore = state.getScore();
state.neighbor((double)nowTime / timeLimit);
if (bestScore < state.getScore()) {
bestScore = state.getScore();
bestState = state.copy();
}
if (state.getScore() < prevScore) {
state = state.rollback();
}
}
return bestState;
}
State annealing(State state, double startTemp, double endTemp, long timeLimit) {
State bestState = state.copy();
double bestScore = state.getScore();
while (true) {
long nowTime = System.currentTimeMillis() - startTime;
if (nowTime >= timeLimit) {
break;
}
double prevScore = state.getScore();
int nid = state.neighbor((double)nowTime / timeLimit);
if (nid == -1) {
continue;
}
if (bestScore < state.getScore()) {
bestScore = state.getScore();
bestState = state.copy();
}
double diff = state.getScore() - prevScore;
double temp = startTemp + (endTemp - startTemp) * nowTime / timeLimit;
double p = diff > 0 ? 1 : Math.exp(diff / temp);
if (rand.nextDouble() >= p) {
state = state.rollback();
}
}
return bestState;
}
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;
public 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;
}
}
}