結果
| 問題 | No.5007 Steiner Space Travel |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2022-08-04 23:18:58 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 23,232 bytes |
| コンパイル時間 | 3,471 ms |
| 実行使用メモリ | 73,340 KB |
| スコア | 2,961,930 |
| 最終ジャッジ日時 | 2022-08-04 23:19:38 |
| 合計ジャッジ時間 | 37,518 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | TLE | - |
| testcase_02 | TLE | - |
| testcase_03 | AC | 992 ms
70,392 KB |
| testcase_04 | AC | 996 ms
70,232 KB |
| testcase_05 | AC | 988 ms
71,380 KB |
| testcase_06 | AC | 987 ms
72,032 KB |
| testcase_07 | TLE | - |
| testcase_08 | TLE | - |
| testcase_09 | TLE | - |
| testcase_10 | AC | 994 ms
65,416 KB |
| testcase_11 | AC | 997 ms
73,340 KB |
| testcase_12 | TLE | - |
| testcase_13 | TLE | - |
| testcase_14 | TLE | - |
| testcase_15 | TLE | - |
| testcase_16 | TLE | - |
| testcase_17 | TLE | - |
| testcase_18 | TLE | - |
| testcase_19 | AC | 992 ms
71,848 KB |
| testcase_20 | AC | 987 ms
69,900 KB |
| testcase_21 | AC | 997 ms
70,308 KB |
| testcase_22 | TLE | - |
| testcase_23 | TLE | - |
| testcase_24 | TLE | - |
| testcase_25 | AC | 994 ms
69,880 KB |
| testcase_26 | TLE | - |
| testcase_27 | TLE | - |
| testcase_28 | TLE | - |
| testcase_29 | TLE | - |
ソースコード
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.stream.IntStream;
public class Main {
private int N;
private int M;
private int[] r;
private int[] c;
private int[] r2;
private int[] c2;
private ArrayList<Integer> types;
private ArrayList<Integer> indexes;
private double score;
private int[] bestR2;
private int[] bestC2;
private ArrayList<Integer> bestType;
private ArrayList<Integer> bestIndex;
private double bestScore;
private static final double[] alpha = { 0, 0, 25, 5, 1, };
private int[] countPlanets;
public static SAState sa = new SAState();
public static void main(String[] args) {
new Main().run();
}
private void run() {
read();
greedy();
multiSA();
write();
}
private void write() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
sb.append(bestR2[i] + " " + bestC2[i]).append("\n");
}
final int V = bestType.size();
sb.append(V + 1).append("\n");
int index = 0;
for (int i = 0; i < V; i++) {
if (bestType.get(i) == 1 && bestIndex.get(i) == 0) {
index = i;
}
}
for (int i = 0; i < V; i++) {
sb.append(bestType.get((index + i) % V) + " " + (bestIndex.get((index + i) % V) + 1)).append("\n");
}
sb.append(bestType.get((index + 0) % V) + " " + (bestIndex.get((index + 0) % V) + 1)).append("\n");
System.out.print(sb.toString());
System.out.flush();
}
private void greedy() {
r2 = new int[M];
c2 = new int[M];
for (int i = 0; i < M; i++) {
r2[i] = (int) (500 + 250 * Math.sin(Math.toRadians(i * 360.0 / M)));
c2[i] = (int) (500 + 250 * Math.cos(Math.toRadians(i * 360.0 / M)));
}
bestR2 = new int[M];
bestC2 = new int[M];
types = new ArrayList<>();
indexes = new ArrayList<>();
bestType = new ArrayList<>();
bestIndex = new ArrayList<>();
countPlanets = new int[N];
for (int i = 0; i < N; i++) {
types.add(1);
indexes.add(i);
countPlanets[i]++;
types.add(2);
indexes.add(i * M / N);
}
score = calculateScore();
bestScore = 1e99;
saveBest();
}
private void read() {
try (Scanner in = new Scanner(System.in)) {
N = in.nextInt();
Constants.watch.init();
M = in.nextInt();
r = new int[N];
c = new int[N];
IntStream.range(0, N).forEach(i -> {
r[i] = in.nextInt();
c[i] = in.nextInt();
});
} catch (Exception e) {
e.printStackTrace();
}
}
private void multiSA() {
int numRestart = 1;
double startTime = Constants.watch.getSecond();
double endTime = 1 - 0.2;
double remainTime = endTime - startTime;
double startStartTemperature = 50000;
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.startRange = 200;
sa.endRange = 10;
SA();
}
Utils.debug("multiSA", "score", score2(score), "time", Constants.watch.getSecondString());
}
private double score2(double score) {
return 1e9 / (1e3 + Math.sqrt(score));
}
private void SA() {
double second = Constants.watch.getSecond();
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 5) - 1)) == 0) {
sa.update();
if (sa.time > second) {
second += 1;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%05.3f", score2(score)), String.format("%05.3f", score2(bestScore)), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
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("%05.3f", score2(score)), String.format("%05.3f", score2(bestScore)), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
}
mutate();
}
}
private void mutate() {
double random = 4.2 * Constants.RNG.nextDouble();
if (random < 1) {
reverse();
} else if (random < 2) {
swap();
} else if (random < 3) {
addISS();
} else if (random < 4) {
removeISS();
} else if (random < 4.1) {
addBestISS();
} else if (random < 4.2) {
moveISS();
} else if (random < 7) {
insert();
}
}
private void reverse() {
final int V = types.size();
int i1 = Constants.RNG.nextInt(V);
int i2 = Constants.RNG.nextInt(V - 1);
if (i2 >= i1) {
i2++;
}
if (i1 > i2) {
int swap = i1;
i1 = i2;
i2 = swap;
}
final int a = (i1 - 1 + V) % V;
final int b = i1;
final int c = i2 - 1;
final int d = i2;
double deltaScore = -(calculatePartScore(a, b) + calculatePartScore(c, d)) + (calculatePartScore(a, c) + calculatePartScore(b, d));
if (sa.accept(deltaScore)) {
score += deltaScore;
reverse(types, i1, i2 - 1);
reverse(indexes, i1, i2 - 1);
saveBest();
} else {
}
}
private void swap() {
final int V = types.size();
int i1 = Constants.RNG.nextInt(V);
int i2 = Constants.RNG.nextInt(V - 1);
if (i2 >= i1) {
i2++;
}
if (i1 > i2) {
int swap = i1;
i1 = i2;
i2 = swap;
}
if (i1 == 0 && i2 == V - 1) {
final int a = (i2 - 1 + V) % V;
final int b = i2;
final int e = i1;
final int f = (i1 + 1) % V;
final double before = calculatePartScore(a, b) + calculatePartScore(b, e) + calculatePartScore(e, f);
final double after = calculatePartScore(a, e) + calculatePartScore(e, b) + calculatePartScore(b, f);
double deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
Collections.swap(types, i1, i2);
Collections.swap(indexes, i1, i2);
saveBest();
} else {
}
} else if (i1 + 1 == i2) {
final int a = (i1 - 1 + V) % V;
final int b = i1;
final int e = i2;
final int f = (i2 + 1) % V;
final double before = calculatePartScore(a, b) + calculatePartScore(b, e) + calculatePartScore(e, f);
final double after = calculatePartScore(a, e) + calculatePartScore(e, b) + calculatePartScore(b, f);
double deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
Collections.swap(types, i1, i2);
Collections.swap(indexes, i1, i2);
saveBest();
} else {
}
} else {
final int a = (i1 - 1 + V) % V;
final int b = i1;
final int c = (i1 + 1) % V;
final int d = (i2 - 1 + V) % V;
final int e = i2;
final int f = (i2 + 1) % V;
final double before = calculatePartScore(a, b) + calculatePartScore(b, c) + calculatePartScore(d, e) + calculatePartScore(e, f);
final double after = calculatePartScore(a, e) + calculatePartScore(e, c) + calculatePartScore(d, b) + calculatePartScore(b, f);
double deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
Collections.swap(types, i1, i2);
Collections.swap(indexes, i1, i2);
saveBest();
} else {
}
}
}
private void insert() {
int i1 = Constants.RNG.nextInt(types.size());
int i2 = Constants.RNG.nextInt(types.size() - 1);
int i3 = Constants.RNG.nextInt(types.size() - 2);
if (i2 > i1) {
i2++;
}
if (i3 > i1) {
i3++;
}
if (i3 > i2) {
i3++;
}
if (i1 > i2) {
int swap = i1;
i1 = i2;
i2 = swap;
}
if (i1 > i3) {
int swap = i1;
i1 = i3;
i3 = swap;
}
if (i2 > i3) {
int swap = i2;
i2 = i3;
i3 = swap;
}
ArrayList<Integer> copyTypes = new ArrayList<>();
ArrayList<Integer> copyIndexes = new ArrayList<>();
for (int i = 0; i < types.size(); i++) {
copyTypes.add(types.get(i));
copyIndexes.add(indexes.get(i));
}
types.clear();
indexes.clear();
for (int i = 0; i < i1; i++) {
types.add(copyTypes.get(i));
indexes.add(copyIndexes.get(i));
}
for (int i = i2; i < i3; i++) {
types.add(copyTypes.get(i));
indexes.add(copyIndexes.get(i));
}
for (int i = i1; i < i2; i++) {
types.add(copyTypes.get(i));
indexes.add(copyIndexes.get(i));
}
for (int i = i3; i < copyTypes.size(); i++) {
types.add(copyTypes.get(i));
indexes.add(copyIndexes.get(i));
}
double deltaScore = calculateScore() - score;
if (sa.accept(deltaScore)) {
score += deltaScore;
saveBest();
} else {
types.clear();
indexes.clear();
for (int i = 0; i < copyTypes.size(); i++) {
types.add(copyTypes.get(i));
indexes.add(copyIndexes.get(i));
}
}
}
private void moveISS() {
final int i = Constants.RNG.nextInt(M);
final int currentR2 = r2[i];
final int currentC2 = c2[i];
final int n = Constants.RNG.nextInt(N);
final int random = Constants.RNG.nextInt(3);
if (random == 0) {
r2[i] = Constants.RNG.nextInt(1001);
c2[i] = Constants.RNG.nextInt(1001);
} else if (random == 1) {
r2[i] = r[n];
c2[i] = c[n];
} else {
r2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
c2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
r2[i] = Math.min(1000, Math.max(0, r2[i]));
c2[i] = Math.min(1000, Math.max(0, c2[i]));
}
double deltaScore = calculateScore() - score;
if (sa.accept(deltaScore)) {
score += deltaScore;
saveBest();
} else {
r2[i] = currentR2;
c2[i] = currentC2;
}
}
private void moveISS3() {
final int i = Constants.RNG.nextInt(M);
final int currentR2 = r2[i];
final int currentC2 = c2[i];
if (Constants.RNG.nextInt(2) == 0) {
r2[i] = Constants.RNG.nextInt(1001);
c2[i] = Constants.RNG.nextInt(1001);
} else {
r2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
c2[i] += (int) (-sa.range + 2 * sa.range * Constants.RNG.nextDouble());
r2[i] = Math.min(1000, Math.max(0, r2[i]));
c2[i] = Math.min(1000, Math.max(0, c2[i]));
}
double deltaScore = calculateScore() - score;
if (sa.accept(deltaScore)) {
score += deltaScore;
saveBest();
} else {
r2[i] = currentR2;
c2[i] = currentC2;
}
}
private void moveISS2() {
final int i = Constants.RNG.nextInt(M);
final int currentR2 = r2[i];
final int currentC2 = c2[i];
if (Constants.RNG.nextInt(2) == 0) {
r2[i] = Constants.RNG.nextInt(1001);
c2[i] = Constants.RNG.nextInt(1001);
} else {
r2[i] += -100 + Constants.RNG.nextInt(201);
c2[i] += -100 + Constants.RNG.nextInt(201);
r2[i] = Math.min(1000, Math.max(0, r2[i]));
c2[i] = Math.min(1000, Math.max(0, c2[i]));
}
double deltaScore = calculateScore() - score;
if (sa.accept(deltaScore)) {
score += deltaScore;
saveBest();
} else {
r2[i] = currentR2;
c2[i] = currentC2;
}
}
private void addISS() {
final int V = types.size();
final int i = Constants.RNG.nextInt(V);
final int type = 1 + Constants.RNG.nextInt(2);
final int index = Constants.RNG.nextInt(M);
if (type == 1) {
if (countPlanets[index] >= 5) {
return;
}
}
types.add(type);
indexes.add(index);
final int a = (i - 1 + V) % V;
final int b = i;
double deltaScore = -(calculatePartScore(a, b)) + (calculatePartScore(a, V) + calculatePartScore(V, b));
Integer remove = types.remove(V);
Integer remove2 = indexes.remove(V);
if (sa.accept(deltaScore)) {
score += deltaScore;
types.add(i, type);
indexes.add(i, index);
if (type == 1) {
countPlanets[index]++;
}
saveBest();
} else {
}
}
private void addBestISS() {
final int V = types.size();
final int i = Constants.RNG.nextInt(V);
double best = 1e99;
int index = -1;
for (int m = 0; m < M; m++) {
types.add(2);
indexes.add(m);
final int a = (i - 1 + V) % V;
final int b = i;
double deltaScore = -(calculatePartScore(a, b)) + (calculatePartScore(a, V) + calculatePartScore(V, b));
if (deltaScore < best) {
best = deltaScore;
index = m;
}
Integer remove = types.remove(V);
Integer remove2 = indexes.remove(V);
}
if (sa.accept(best)) {
score += best;
types.add(i, 2);
indexes.add(i, index);
saveBest();
} else {
}
}
private void removeISS() {
final int V = types.size();
final int i = Constants.RNG.nextInt(V);
if (types.get(i) == 1) {
if (countPlanets[indexes.get(i)] <= 1) {
return;
}
}
final int a = (i - 1 + V) % V;
final int b = i;
final int c = (i + 1) % V;
double deltaScore = -(calculatePartScore(a, b) + calculatePartScore(b, c)) + (calculatePartScore(a, c));
if (sa.accept(deltaScore)) {
score += deltaScore;
if (types.get(i) == 1) {
countPlanets[indexes.get(i)]--;
}
types.remove(i);
indexes.remove(i);
saveBest();
} else {
}
}
private void saveBest() {
if (score < bestScore) {
bestScore = score;
for (int i = 0; i < M; i++) {
bestR2[i] = r2[i];
bestC2[i] = c2[i];
}
bestType.clear();
bestIndex.clear();
for (int i = 0; i < types.size(); i++) {
bestType.add(types.get(i));
bestIndex.add(indexes.get(i));
}
}
}
private double calculateScore() {
double score = 0;
final int V = types.size();
for (int i = 0; i < V; i++) {
score += calculatePartScore(i, (i + 1) % V);
}
return score;
}
private double calculatePartScore(int i, int j) {
return alpha[types.get(i) + types.get(j)] * distance(getR(i), getC(i), getR(j), getC(j));
}
private int getR(int i) {
return types.get(i) == 1 ? r[indexes.get(i)] : r2[indexes.get(i)];
}
private int getC(int i) {
return types.get(i) == 1 ? c[indexes.get(i)] : c2[indexes.get(i)];
}
private double distance(int r, int c, int r2, int c2) {
double dr = r - r2;
double dc = c - c2;
return dr * dr + dc * dc;
}
private void reverse(ArrayList<Integer> a, int i, int j) {
for (int l = i, r = j; l < r; l++, r--) {
Collections.swap(a, l, r);
}
}
private void swap(int[] a, int i, int j) {
int swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
final class Utils {
private Utils() {
}
public static final void debug(Object... o) {
// System.err.println(toString(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));
}
}
}
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 ? Constants.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() {
double time0to1 = elapsedPercentage(startTime, endTime, time);
double startY = startRange;
double endY = endRange;
range = interpolate(startY, endY, time0to1);
}
public void updateTime() {
time = useTime ? Constants.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[Constants.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[Constants.RNG.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
}
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;
}
}
interface Constants {
Watch watch = new Watch();
PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());
}