結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 2022-07-30 17:56:19 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 948 ms / 1,000 ms |
コード長 | 22,719 bytes |
コンパイル時間 | 2,981 ms |
実行使用メモリ | 58,416 KB |
スコア | 8,837,448 |
最終ジャッジ日時 | 2022-07-30 17:56:53 |
合計ジャッジ時間 | 33,611 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
import java.util.ArrayList;import java.util.Arrays;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, };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<>();for (int i = 0; i < N; i++) {types.add(1);indexes.add(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.25;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 index = Constants.RNG.nextInt(M);types.add(2);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, 2);indexes.add(i, 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) != 2) {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;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());}