EvbCFfp1XB

problem and my answer.

March 2017

Rank 11/80

アプローチ stitch の数が多いとき:
  1. cross stitch 単位で、任意の cross stitch からの距離が0の imaginary cross stitch を加えて Travelling Salesman Problem として解く。
  2. 直前の cross stitch と次の cross stitch からの距離が短い縫い方を貪欲法で見つける。
  3. 2opt で改善する。
stitch の数が少ないとき:
  1. stitch 単位で、任意の stitch からの距離が0の imaginary stitch を加えて、 Travelling Salesman Problem として解く。

Approach(Google Translate) When the number of stitches is large:

  1. In cross stitch unit, add imaginary cross stitch with distance 0 from arbitrary cross stitch and solve it as Traveling Salesman Problem.
  2. Find greedy how to sew a short distance from the previous cross stitch and the next cross stitch.
  3. Improve by 2opt.

When the number of stitches is small:

  1. Add imaginary stitch with distance 0 from arbitrary stitch in stitch unit and solve it as Traveling Salesman Problem.


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

public class CrossStitch {
private double lengthFront;
private double lengthBack;

private int S;
private Watch watch = new Watch();
private HashMap<Integer, ArrayList<Point>> colorToPoints = new HashMap<>();
private HashMap<Integer, ArrayList<Stitch>> colorToStitches = new HashMap<>();

private int numStitches;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distancesStitchTo4PointOfStitch;
private int[] index2stitch;
private int[] stitch2index;
private IntArray[] stitch2nearestStitches;
private boolean[] startFromUpper;
private HashMap<Integer, HashMap<Integer, Integer>> stitch2nearestStitchIndex2index;

private int sumLoops;
private int sumTries;
private int sumAccepts;
private ArrayList<Stitch> stitches;

public String[] embroider(String[] pattern) {
init(pattern);

ArrayList<String> ret = new ArrayList<>();

double initTime = watch.getSecond();

double eachColorTime = (1 * 9.5 - initTime) / colorToPoints.keySet().size();

double sumBackLength = 0;

for (Integer color : colorToPoints.keySet()) {

eachColorWatch.init();

if (colorToPoints.get(color).size() < 750) {

ArrayList<Stitch> stitches = colorToStitches.get(color);
stitches.add(new Stitch(new Point(-1, -1), new Point(-1, -1)));
this.stitches = stitches;

numStitches = stitches.size();

setDistance(stitches);

initializeIndex(stitches);

improve(eachColorTime, stitches);

sumBackLength += calculateScore();

numStitches--;
int startIndex = -1;
for (int i = 0; i < index2stitch.length; i++) {
if (index2stitch[i] == numStitches) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[numStitches];
for (int i = startIndex + 1; i < startIndex + index2stitch.length; i++) {
path.add(stitches.get(index2stitch[i % index2stitch.length]));
isUpper2[i - (startIndex + 1)] = startFromUpper[index2stitch[i % index2stitch.length]];
}

makeResult(ret, color, path, isUpper2);

} else {
ArrayList<Point> points = colorToPoints.get(color);

int[] x = new int[points.size() + 1];
int[] y = new int[points.size() + 1];
for (int i = 0; i < points.size(); i++) {
x[i] = points.get(i).c;
y[i] = points.get(i).r;
}
x[points.size()] = -2;
y[points.size()] = -2;

EuclideanTravellingSalesmanProblem tsp = new EuclideanTravellingSalesmanProblem();
int[] order = tsp.getOrder(x, y, eachColorTime);

sumLoops += tsp.loop;
sumTries += tsp.tries;
sumAccepts += tsp.ac;

int startIndex = -1;
for (int i = 0; i < order.length; i++) {
if (order[i] == points.size()) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Point> pathStitch = new ArrayList<>();
for (int i = startIndex + 1; i < startIndex + order.length; i++) {
pathStitch.add(points.get(order[i % order.length]));
}

ArrayList<Stitch> stitches = greedy(color, pathStitch);
stitches.add(new Stitch(new Point(-2, -2), new Point(-2, -2)));

boolean[] startFromUpper = new boolean[stitches.size()];
for (int i = 0; i < stitches.size(); i++) {
startFromUpper[i] = true;
Stitch stitch = stitches.get(i);
if (stitch.upper.r < stitch.lower.r) {
startFromUpper[i] = !true;

Point swap = stitch.upper;
stitch.upper = stitch.lower;
stitch.lower = swap;
}
}

for (int k = 0; k < 5; k++) {
greedy2opt(stitches, startFromUpper);
}
startIndex = -1;
for (int i = 0; i < stitches.size(); i++) {
if (stitches.get(i).upper.r < 0) {
startIndex = i;
break;
}
}

if (startIndex == -1) {
throw new AssertionError();
}

ArrayList<Stitch> path = new ArrayList<>();
boolean[] isUpper2 = new boolean[stitches.size() - 1];
for (int i = startIndex + 1; i < startIndex + stitches.size(); i++) {
path.add(stitches.get(i % stitches.size()));
isUpper2[i - (startIndex + 1)] = startFromUpper[i % stitches.size()];
}

makeResult(ret, color, path, isUpper2);
}

}

int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
lengthFront = Math.sqrt(2) * 2 * numPoints;

double score = calculateRawScore(lengthFront, lengthBack);
Utils.debug("score", (int) (1e6 * score), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * lengthBack), "time", watch.getSecondString());
Utils.debug("score", (int) (1e6 * calculateRawScore(lengthFront, sumBackLength)), "front", (int) (1e2 * lengthFront), "back", (int) (1e2 * sumBackLength), "time", watch.getSecondString());
Utils.debug("sumLoops", sumLoops, "try/loop", String.format("%.1f%%", (double) 100.0 * sumTries / sumLoops), "AC/try", String.format("%.1f%%", (double) 100.0 * sumAccepts / sumTries));

return (String[]) ret.toArray(new String[ret.size()]);
}

private ArrayList<Stitch> greedy(Integer color, ArrayList<Point> path) {

ArrayList<Stitch> ret = new ArrayList<>();
if (path.size() == 1) {

Point point = path.get(0);

int minD = 0;

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

return ret;
}

Point previousPoint = null;
for (int i = 0; i < path.size() - 1; i++) {
Point point = path.get(i);
Point nextPoint = path.get(i + 1);

if (i == 0) {

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
double distance = distance(point.r + dr[d], point.c + dc[d], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distance < minDistance) {
minDistance = distance;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4]), new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2]), new Point(point.r + dr[minD], point.c + dc[minD])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

} else {

double minDistance = 1e9;
int minD = -1;
int minD2 = -1;
for (int d = 0; d < dr.length; d++) {
if (point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);

{
int d2 = (d + 1) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
{
int d2 = (d + 3) % 4;
double distance = distance(point.r + dr[d2], point.c + dc[d2], nextPoint.r + 0.5, nextPoint.c + 0.5);
if (distanceToPrevious + distance < minDistance) {
minDistance = distanceToPrevious + distance;
minD = d;
minD2 = d2;
}
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[minD2 ^ 2], point.c + dc[minD2 ^ 2]), new Point(point.r + dr[minD2], point.c + dc[minD2])));

previousPoint = new Point(point.r + dr[minD2], point.c + dc[minD2]);

}
}
{

Point point = path.get(path.size() - 1);

double minDistance = 1e9;
int minD = -1;
for (int d = 0; d < dr.length; d++) {
if (previousPoint != null && point.r + dr[d] == previousPoint.r && point.c + dc[d] == previousPoint.c) {
continue;
}
double distanceToPrevious = distance(point.r + dr[d], point.c + dc[d], previousPoint.r, previousPoint.c);
if (distanceToPrevious < minDistance) {
minDistance = distanceToPrevious;
minD = d;
}
}

if (minD == -1) {
throw new AssertionError();
}

ret.add(new Stitch(new Point(point.r + dr[minD], point.c + dc[minD]), new Point(point.r + dr[minD ^ 2], point.c + dc[minD ^ 2])));
ret.add(new Stitch(new Point(point.r + dr[((minD + 1) % 4) ^ 2], point.c + dc[((minD + 1) % 4) ^ 2]), new Point(point.r + dr[(minD + 1) % 4], point.c + dc[(minD + 1) % 4])));

previousPoint = new Point(point.r + dr[minD], point.c + dc[minD]);

}
return ret;
}

private int greedyLoop = 0;
private int greedyTry = 0;
private int greedyAC = 0;
private int greedyImprove = 0;

private void greedy2opt(ArrayList<Stitch> stitches, boolean[] startFromUpper) {
for (int i = 0; i < stitches.size(); i++) {
for (int i2 = i + 1; i2 <= i + 64; i2++) {
greedyLoop++;
if (i2 < 0 || i2 >= stitches.size()) {
continue;
}

int B = i;
int A = B - 1;
if (A < 0) {
A = stitches.size() - 1;
}

int C = i2;
int D = C + 1;
if (D == stitches.size()) {
D = 0;
}

Point pointA = startFromUpper[A] ? stitches.get(A).lower : stitches.get(A).upper;
Point pointB = startFromUpper[B] ? stitches.get(B).upper : stitches.get(B).lower;
double distanceAB = distance(pointA.r, pointA.c, pointB.r, pointB.c);
if (distanceAB < 1e-9) {
distanceAB = 1e9;
}
if (pointA.r < 0 || pointB.r < 0) {
distanceAB = 0;
}
Point pointC = startFromUpper[C] ? stitches.get(C).lower : stitches.get(C).upper;
Point pointD = startFromUpper[D] ? stitches.get(D).upper : stitches.get(D).lower;
double distanceCD = distance(pointC.r, pointC.c, pointD.r, pointD.c);
if (distanceCD < 1e-9) {
distanceCD = 1e9;
}
if (pointC.r < 0 || pointD.r < 0) {
distanceCD = 0;
}
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(pointA.r, pointA.c, pointC.r, pointC.c);
if (distanceAC < 1e-9) {
continue;
}
if (pointA.r < 0 || pointC.r < 0) {
distanceAC = 0;
}
double distanceBD = distance(pointB.r, pointB.c, pointD.r, pointD.c);
if (distanceBD < 1e-9) {
continue;
}
if (pointB.r < 0 || pointD.r < 0) {
distanceBD = 0;
}
double AC_BD = distanceAC + distanceBD;

greedyTry++;
if (AC_BD < AB_CD) {
greedyAC++;
greedyImprove += AB_CD - AC_BD;
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
if (l < r) {
Collections.swap(stitches, l, r);

boolean swap = !startFromUpper[l];
startFromUpper[l] = !startFromUpper[r];
startFromUpper[r] = swap;
} else {
startFromUpper[l] = !startFromUpper[l];
}
}
}
}

}
}
}

private double calculateRawScore(double front, double back) {
return Math.max(0, Math.pow((5 - back / front) / 5, 3));
}

private void findNearestCities(ArrayList<Stitch> stitches) {
stitch2nearestStitches = new IntArray[numStitches];
for (int i = 0; i < numStitches; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < numStitches; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distancesStitchTo4PointOfStitch[2 * i][2 * j], j));
}
Collections.sort(list);
stitch2nearestStitches[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / numStitches), list.size()); j++) {
stitch2nearestStitches[i].add(list.get(j).second);
}
}
}

Watch eachColorWatch = new Watch();

private void improve(double second, ArrayList<Stitch> stitches) {
double score = calculateScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.0, temperature = startTemperature;
double startTime = eachColorWatch.getSecond(), endTime = second, time = startTime;
int loop = 0;

int mask = (1 << 8) - 1;

for (;; loop++) {
if ((loop & mask) == mask) {
time = eachColorWatch.getSecond();

if (time >= endTime) {
sumLoops += loop;
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

if (xorShift.nextDouble() < 1.5) {
int B = 1 + (int) ((numStitches - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray nearestStitches = stitch2nearestStitches[index2stitch[A]];
int randomIndex = (int) (nearestStitches.length * xorShift.nextDouble());
int stitch = nearestStitches.values[randomIndex];
int c = stitch2index[stitch];

int C = c;
int D = c + 1;
if (D == numStitches) {
D = 0;
}
double distanceAB = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2));
double distanceCD = distance(index2stitch[C], index2stitch[D], (startFromUpper[index2stitch[C]] ? 1 : 0) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AB_CD = distanceAB + distanceCD;
double distanceAC = distance(index2stitch[A], index2stitch[C], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 2 : 0));
double distanceBD = distance(index2stitch[B], index2stitch[D], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[D]] ? 0 : 2));
double AC_BD = distanceAC + distanceBD;

sumTries++;
if (AC_BD <= AB_CD || (-AC_BD + AB_CD > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-AC_BD + AB_CD) / (score * temperature)))) {
if (!isValidCurrentFlip(A, C)) {
sumTries--;
continue;
}
if (!isValidFlipCurrent(B, D)) {
sumTries--;
continue;
}
sumAccepts++;

score += (AC_BD - AB_CD);
if (B <= C) {
for (int l = B, r = C; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
} else {
for (int l = C + 1, r = B - 1; l <= r; l++, r--) {
int swap = index2stitch[l];
index2stitch[l] = index2stitch[r];
index2stitch[r] = swap;

stitch2index[index2stitch[l]] = l;
stitch2index[index2stitch[r]] = r;

startFromUpper[index2stitch[l]] = !startFromUpper[index2stitch[l]];
if (l < r) {
startFromUpper[index2stitch[r]] = !startFromUpper[index2stitch[r]];
}
}
}
}
} else {

int A = (int) (numStitches * xorShift.nextDouble());
int B = A + 1;
if (B == numStitches) {
B = 0;
}
int C = B + 1;
if (C == numStitches) {
C = 0;
}

if (!isValidCurrentFlip(A, B)) {
continue;
}
if (!isValidFlipCurrent(B, C)) {
continue;
}
double ABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 0 : 2)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 1 : 0) + (startFromUpper[index2stitch[C]] ? 0 : 2));
double nextABC = distance(index2stitch[A], index2stitch[B], (startFromUpper[index2stitch[A]] ? 1 : 0) + (startFromUpper[index2stitch[B]] ? 2 : 0)) + distance(index2stitch[B], index2stitch[C], (startFromUpper[index2stitch[B]] ? 0 : 1) + (startFromUpper[index2stitch[C]] ? 0 : 2));

if (nextABC <= ABC || (-nextABC + ABC > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-nextABC + ABC) / (score * temperature)))) {

score += (nextABC - ABC);

startFromUpper[index2stitch[B]] = !startFromUpper[index2stitch[B]];

}

}
}
}

private boolean isValidCurrentFlip(int A, int C) {
if (startFromUpper[index2stitch[A]]) {
Point pointALower = stitches.get(index2stitch[A]).lower;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointALower.r == pointCLooer.r && pointALower.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointALower.r == pointCUpper.r && pointALower.c == pointCUpper.c) {
return false;
}
}
} else {
Point pointAUpper = stitches.get(index2stitch[A]).upper;
if (startFromUpper[index2stitch[C]]) {
Point pointCLooer = stitches.get(index2stitch[C]).lower;
if (pointAUpper.r == pointCLooer.r && pointAUpper.c == pointCLooer.c) {
return false;
}
} else {
Point pointCUpper = stitches.get(index2stitch[C]).upper;
if (pointAUpper.r == pointCUpper.r && pointAUpper.c == pointCUpper.c) {
return false;
}
}
}
return true;
}

private boolean isValidFlipCurrent(int B, int D) {
if (startFromUpper[index2stitch[B]]) {
Point pointBUpper = stitches.get(index2stitch[B]).upper;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBUpper.r == pointDUpper.r && pointBUpper.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBUpper.r == pointDLower.r && pointBUpper.c == pointDLower.c) {
return false;
}
}
} else {
Point pointBLower = stitches.get(index2stitch[B]).lower;
if (startFromUpper[index2stitch[D]]) {
Point pointDUpper = stitches.get(index2stitch[D]).upper;
if (pointBLower.r == pointDUpper.r && pointBLower.c == pointDUpper.c) {
return false;
}
} else {
Point pointDLower = stitches.get(index2stitch[D]).lower;
if (pointBLower.r == pointDLower.r && pointBLower.c == pointDLower.c) {
return false;
}
}
}
return true;
}

private double distance(int AFrom, int BTo, int deltaIndex) {
if (stitches.get(AFrom).upper.r < 0 || stitches.get(BTo).upper.r < 0) {
return 0;
}
int r0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.r : stitches.get(AFrom).lower.r;
int c0 = (deltaIndex & 1) == 0 ? stitches.get(AFrom).upper.c : stitches.get(AFrom).lower.c;
int r1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.r : stitches.get(BTo).lower.r;
int c1 = (deltaIndex & 2) == 0 ? stitches.get(BTo).upper.c : stitches.get(BTo).lower.c;
return distance(r0, c0, r1, c1);
}

private void initializeIndex(ArrayList<Stitch> stitches) {
index2stitch = new int[numStitches];
stitch2index = new int[numStitches];
startFromUpper = new boolean[numStitches];
for (int i = 0; i < index2stitch.length; i++) {
index2stitch[i] = i;
stitch2index[index2stitch[i]] = i;
startFromUpper[i] = true;
if (i == 0) {

} else {
if (startFromUpper[i - 1]) {
if (stitches.get(i).upper.r == stitches.get(i - 1).lower.r && stitches.get(i).upper.c == stitches.get(i - 1).lower.c) {
startFromUpper[i] = !true;
}
} else {
if (stitches.get(i).upper.r == stitches.get(i - 1).upper.r && stitches.get(i).upper.c == stitches.get(i - 1).upper.c) {
startFromUpper[i] = !true;
}
}
}
}

}

private void setDistance(ArrayList<Stitch> stitches) {
int n = 10;
int clusterSize = (S + 1) / n + ((S + 1) % n > 0 ? 1 : 0);
IntArray[][] cluster = new IntArray[clusterSize][clusterSize];
for (int r = 0; r < cluster.length; r++) {
for (int c = 0; c < cluster[r].length; c++) {
cluster[r][c] = new IntArray();
}
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);
int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;
cluster[clusterR][clusterC].add(i);
}

PriorityQueue[] distanceStitchToStitch = new PriorityQueue[numStitches];
for (int i = 0; i < distanceStitchToStitch.length; i++) {
distanceStitchToStitch[i] = new PriorityQueue<Pair<Double, Integer>>(new Comparator<Pair<Double, Integer>>() {
@Override
public int compare(Pair<Double, Integer> o1, Pair<Double, Integer> o2) {
if (o1.first.doubleValue() > o2.first.doubleValue()) {
return -1;
}
if (o1.first.doubleValue() < o2.first.doubleValue()) {
return 1;
}
return 0;
}
});
}
for (int i = 0; i < numStitches; i++) {
Stitch stitch = stitches.get(i);

int clusterR = stitch.upper.r / n;
int clusterC = stitch.upper.c / n;

for (int r = clusterR - 1; r <= clusterR + 1; r++) {
if (r < 0 || r >= cluster.length) {
continue;
}
for (int c = clusterC - 1; c <= clusterC + 1; c++) {
if (c < 0 || c >= cluster[r].length) {
continue;
}

for (int k = 0; k < cluster[r][c].length; k++) {

int j = cluster[r][c].values[k];
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

{

int j = numStitches - 1;
if (j == i) {
continue;
}
Stitch stitchJ = stitches.get(j);
if (stitch.upper.r < 0 || stitchJ.upper.r < 0) {
distanceStitchToStitch[i].add(new Pair<Double, Integer>(0.0, j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
} else {
double dx = stitchJ.upper.c - stitch.upper.c;
double dy = stitchJ.upper.r - stitch.upper.r;
distanceStitchToStitch[i].add(new Pair<Double, Integer>(Math.sqrt(dx * dx + dy * dy), j));
if (distanceStitchToStitch[i].size() > 32) {
distanceStitchToStitch[i].poll();
}
}

}

}
}
}

distancesStitchTo4PointOfStitch = new double[numStitches][4 * 32];
stitch2nearestStitches = new IntArray[numStitches];
stitch2nearestStitchIndex2index = new HashMap<Integer, HashMap<Integer, Integer>>();

for (int i = 0; i < numStitches; i++) {
stitch2nearestStitches[i] = new IntArray(32);
for (int j = 0; !distanceStitchToStitch[i].isEmpty(); j++) {
Pair<Double, Integer> distanceAndStitchIndexPair = (Pair<Double, Integer>) distanceStitchToStitch[i].poll();
int k = 4 * j;

Stitch stitchFrom = stitches.get(i);
Stitch stitchTo = stitches.get(distanceAndStitchIndexPair.second.intValue());
if (stitchFrom.upper.r < 0 || stitchTo.upper.r < 0) {
distancesStitchTo4PointOfStitch[i][k + 0] = 0;
distancesStitchTo4PointOfStitch[i][k + 1] = 0;
distancesStitchTo4PointOfStitch[i][k + 2] = 0;
distancesStitchTo4PointOfStitch[i][k + 3] = 0;
} else {
distancesStitchTo4PointOfStitch[i][k + 0] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 1] = distance(stitchFrom.upper.r, stitchFrom.upper.c, stitchTo.lower.r, stitchTo.lower.c);
distancesStitchTo4PointOfStitch[i][k + 2] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.upper.r, stitchTo.upper.c);
distancesStitchTo4PointOfStitch[i][k + 3] = distance(stitchFrom.lower.r, stitchFrom.lower.c, stitchTo.lower.r, stitchTo.lower.c);
}
stitch2nearestStitches[i].add(distanceAndStitchIndexPair.second.intValue());

if (stitch2nearestStitchIndex2index.get(i) == null) {
stitch2nearestStitchIndex2index.put(i, new HashMap<Integer, Integer>());
}
stitch2nearestStitchIndex2index.get(i).put(distanceAndStitchIndexPair.second, k);
}
}
}

private double[] currentDistance;

private double calculateScore() {
double score = 0.0;
currentDistance = new double[numStitches];
for (int i = 0; i < numStitches; i++) {
int j = i + 1;
if (j == numStitches) {
j = 0;
}
int from = index2stitch[i];
int to = index2stitch[j];
double distance = distance(from, to, (startFromUpper[from] ? 1 : 0) + (startFromUpper[to] ? 0 : 2));
score += distance;
currentDistance[from] = distance;
}
return score;
}

private static final int[] dr = new int[] { 0, 0, 1, 1, };
private static final int[] dc = new int[] { 0, 1, 1, 0, };

private void makeResult(ArrayList<String> ret, Integer color, ArrayList<Stitch> path, boolean[] isUpper) {
ret.add("" + (char) (color + 'a'));

for (int i = 0; i < path.size(); i++) {

Stitch stitch = path.get(i);

if (isUpper[i]) {
ret.add(stitch.upper.r + " " + stitch.upper.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.upper.r, stitch.upper.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.lower.r + " " + stitch.lower.c);
lengthFront += Math.sqrt(2);
} else {
ret.add(stitch.lower.r + " " + stitch.lower.c);
if (i == 0) {
lengthBack += 0;
} else {
Stitch previousStitch = path.get(i - 1);
if (isUpper[i - 1]) {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.lower.r, previousStitch.lower.c);
} else {
lengthBack += distance(stitch.lower.r, stitch.lower.c, previousStitch.upper.r, previousStitch.upper.c);
}
}
ret.add(stitch.upper.r + " " + stitch.upper.c);
lengthFront += Math.sqrt(2);
}

}
}

private void init(String[] pattern) {
S = pattern.length;

for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {

char charAt = pattern[r].charAt(c);
if (charAt == '.') {
continue;
}

int color = charAt - 'a';

if (colorToPoints.get(color) == null) {
colorToPoints.put(color, new ArrayList<Point>());
}
colorToPoints.get(color).add(new Point(r, c));

if (colorToStitches.get(color) == null) {
colorToStitches.put(color, new ArrayList<Stitch>());
}
colorToStitches.get(color).add(new Stitch(new Point(r, c), new Point(r + 1, c + 1)));
colorToStitches.get(color).add(new Stitch(new Point(r + 1, c), new Point(r, c + 1)));
}
}

{
int numColors = colorToPoints.keySet().size();
int numPoints = 0;
for (Integer color : colorToPoints.keySet()) {
numPoints += colorToPoints.get(color).size();
}
Utils.debug("S", S, "numColors", numColors, "numPoints", numPoints);
}
}

private double distance(double r0, double c0, double r1, double c1) {
double dr = r1 - r0;
double dc = c1 - c0;
return Math.sqrt(dr * dr + dc * dc);
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int S = Integer.parseInt(br.readLine());
String[] pattern = new String[S];
for (int i = 0; i < S; ++i) {
pattern[i] = br.readLine();
}

CrossStitch cs = new CrossStitch();
String[] ret = cs.embroider(pattern);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Point {
int r;
int c;

public Point(int r, int c) {
super();
this.r = r;
this.c = c;
}
}

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);
}

}

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 EuclideanTravellingSalesmanProblem {
private int N;
private int[] x;
private int[] y;
private XorShift xorShift = new XorShift(System.nanoTime());
private double[][] distance;
private int[] index2city;
private int[] city2index;
private IntArray[] city2nearestCities;

private Watch watch = new Watch();

public int[] getOrder(int[] x, int[] y, double second) {
watch.init();

this.N = x.length;
this.x = x;
this.y = y;
setDistance();
findNearestCities();
initializeIndex();
improve(second);
return index2city;
}

private void findNearestCities() {
city2nearestCities = new IntArray[N];
for (int i = 0; i < N; i++) {
ArrayList<Pair<Double, Integer>> list = new ArrayList<>();
for (int j = 0; j < N; j++) {
if (j == i) {
continue;
}
list.add(new Pair<Double, Integer>(distance[i][j], j));
}
Collections.sort(list);
city2nearestCities[i] = new IntArray();
for (int j = 0; j < Math.min(Math.max(20, 10000 / N), list.size()); j++) {
city2nearestCities[i].add(list.get(j).second);
}
}
}

int loop = 0;
int tries = 0;
int ac = 0;

private void improve(double second) {
double score = getScore();
double endTemperature = 0, startTemperature = 1e-3, expTemperature = 1.5, temperature = startTemperature;
double startTime = watch.getSecond(), endTime = second, time = startTime;

int mask = (1 << 8) - 1;

for (;; loop++) {
if ((loop & mask) == mask) {
time = watch.getSecond();

if (time >= endTime) {
break;
}

temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature);

}

int B = 1 + (int) ((N - 1) * xorShift.nextDouble());
int A = B - 1;
IntArray s = city2nearestCities[index2city[A]];
int c = city2index[s.values[(int) (s.length * xorShift.nextDouble())]];

int C = c;
int D = c + 1;
if (D == N) {
D = 0;
}
double ABCDEF = distance[index2city[A]][index2city[B]] + distance[index2city[C]][index2city[D]];
double ACBDEF = distance[index2city[A]][index2city[C]] + distance[index2city[B]][index2city[D]];
tries++;
if (ACBDEF <= ABCDEF || (-ACBDEF + ABCDEF > -10 * (score * temperature) && (xorShift.nextInt() & 2147483647) < 1 << (int) (31.5 + (-ACBDEF + ABCDEF) / (score * temperature)))) {
ac++;
score = score + (ACBDEF - ABCDEF);

if (B <= C) {
for (int l = B, r = C; l < r; l++, r--) {
int swap = index2city[l];
index2city[l] = index2city[r];
index2city[r] = swap;
city2index[index2city[l]] = l;
city2index[index2city[r]] = r;
}
} else {
for (int l = C + 1, r = B - 1; l < r; l++, r--) {
int swap = index2city[r];
index2city[r] = index2city[l];
index2city[l] = swap;
city2index[index2city[r]] = r;
city2index[index2city[l]] = l;
}
}
}
}
}

private void initializeIndex() {
index2city = new int[N];
city2index = new int[N];
for (int i = 0; i < index2city.length; i++) {
index2city[i] = i;
city2index[index2city[i]] = i;
}

}

private void setDistance() {
distance = new double[N][N];
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < i; j++) {
if (x[i] < 0 || x[j] < 0) {
distance[i][j] = 0;
} else {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
distance[i][j] = Math.sqrt(dx * dx + dy * dy);
}
distance[j][i] = distance[i][j];
}
}
}

private double getScore() {
double score = 0.0;
for (int i = 0; i < N; i++) {
int j = i + 1;
if (j == N) {
j = 0;
}
int from = index2city[i];
int to = index2city[j];
score += distance[from][to];
}
return score;
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

public boolean isEmpty() {
return length == 0;
}

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class Stitch {
Point upper;
Point lower;

public Stitch(Point a, Point b) {
super();
this.upper = a;
this.lower = b;
}

}

Rank 171 / 3508

Approach


最初に最短経路を求めておく。
各ターンは次のような貪欲法:
  • 5ターン目に最初の爆弾をプロダクションが最も大きい最も近い相手の工場に投げる。
    最初の爆弾が届いたら次の爆弾を送る。
  • 軍隊をシミュレーションして、自分の工場が相手のものにならないように、近くの工場から、できるだけ少ない軍隊で助ける。
  • プロダクションが0より大きいニュートラルの工場にできるだけ少ない軍隊を最短経路で送る。
  • プロダクションをできるだけ上げる。
  • 最も近い相手の工場に残りの軍隊を最短経路で送る。

Approach in Engliish(Google Translate)

First find the shortest path.

Each turn is like the following greedy:

  • On the fifth turn, the first bomb is thrown to the closest opponent's factory whose production is the largest.
  • When the first bomb arrives, send the next bomb.
  • Simulate the army and help with as few armies as possible from the nearby factory so that your factory will not be your opponent.
  • Send the fewest possible troops to the neutral factory whose production is greater than 0 on the shortest path.
  • Increase production as much as possible.
  • Send the remaining troops to the closest partner 's factory with the shortest route.


source code


Codingame はソースそのままはダメなんだね。どうりでないと思った。


一ヶ所変化させるシミュレーテッドアニーリングで885点210位

English と言うか Google Translate
I used simulated annealing which changes one place.
885 points
210th place


source code

    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Scanner;
     
    public class Main {
        private static final TimeManager TIME_MANAGER = new TimeManager();
        private static final XorShift RNG = new XorShift();
     
        private static final int DOT = 0;
        private static final int o = 3;
        private static final int x = 4;
        private static final int PLUS = 1;
        private static final int MINUS = 2;
        private static final int WALL = -1;
     
        public static void main(String[] args) {
            new Main().run();
        }
     
        private int score = 0;
     
        int N = 50;
        int[][] board = new int[N][N];
        int[][] boardRotate = new int[N][N];
        IntArray dots = new IntArray();
        int[][] boardRotateDisappear = new int[N + 2][N + 2];
     
        private void run() {
     
            init();
     
            SA();
     
            printSolution();
     
        }
     
        private void printSolution() {
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    board[N - 1 - j][i] = boardRotate[i][j];
                }
            }
     
            Utils.debug("board");
            print(board);
            Utils.debug("boardRotate");
            print(boardRotate);
            Utils.debug("boardRotateDisappear");
            print(boardRotateDisappear);
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (board[i][j] == DOT) {
                        System.out.print('.');
                        continue;
                    }
                    if (board[i][j] == PLUS) {
                        System.out.print('+');
                        continue;
                    }
                    if (board[i][j] == MINUS) {
                        System.out.print('-');
                        continue;
                    }
                    if (board[i][j] == o) {
                        System.out.print('o');
                        continue;
                    }
                    if (board[i][j] == x) {
                        System.out.print('x');
                        continue;
                    }
                }
                System.out.println();
            }
     
        }
     
        private void SA() {
            for (loop = 0, change = 0, ac = 0; !isTimeover(); loop++) {
     
                int before = score;
     
                int v = dots.values[(int) (dots.length * RNG.nextDouble())];
                int r = v >>> 8;
                int c = v & 255;
     
                int current = boardRotate[r][c];
                boardRotate[r][c] = (int) (3 * RNG.nextDouble());
     
                updateDisappear(r);
     
                int after = calculateScore(boardRotateDisappear);
     
                change++;
                if (after >= before || SAaccept(temperature, before, after)) {
                    ac++;
     
                    score = after;
                } else {
                    boardRotate[r][c] = current;
                    updateDisappear(r);
                }
     
            }
        }
     
        private void init() {
            try (Scanner scanner = new Scanner(System.in)) {
                for (int i = 0; i < N; i++) {
                    char[] charArray = scanner.nextLine().toCharArray();
                    for (int j = 0; j < N; j++) {
                        board[i][j] = charArray[j] == '.' ? DOT : charArray[j] == 'o' ? o : x;
                    }
                }
            }
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    boardRotate[i][j] = board[N - 1 - j][i];
                }
            }
     
            Utils.debug("board");
            print(board);
     
            Utils.debug("boardRotate");
            print(boardRotate);
     
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (boardRotate[i][j] == DOT) {
                        dots.add((i << 8) | (j));
                    }
                }
            }
     
            for (int i = 0; i < N + 2; i++) {
                for (int j = 0; j < N + 2; j++) {
                    boardRotateDisappear[i][j] = WALL;
                }
            }
            for (int i = 0; i < N; i++) {
                updateDisappear(i);
            }
     
            Utils.debug("boardRotateDisappear");
            print(boardRotateDisappear);
     
        }
     
        private void print(int[][] board2) {
            for (int i = 0; i < board2.length; i++) {
                for (int j = 0; j < board2[i].length; j++) {
                    if (board2[i][j] == WALL) {
                        System.err.print(' ');
                        continue;
                    }
                    if (board2[i][j] == DOT) {
                        System.err.print('.');
                        continue;
                    }
                    if (board2[i][j] == PLUS) {
                        System.err.print('+');
                        continue;
                    }
                    if (board2[i][j] == MINUS) {
                        System.err.print('-');
                        continue;
                    }
                    if (board2[i][j] == o) {
                        System.err.print('o');
                        continue;
                    }
                    if (board2[i][j] == x) {
                        System.err.print('x');
                        continue;
                    }
                }
                System.err.println();
            }
        }
     
        private void updateDisappear(int i) {
            int j2 = 0;
            for (int j = 0; j < N; j++) {
                if (boardRotate[i][j] == DOT) {
                    continue;
                }
                if (boardRotate[i][j] == MINUS) {
                    for (; j2 < j; j2++) {
                        boardRotateDisappear[i + 1][1 + j2] = WALL;
                    }
                    boardRotateDisappear[i + 1][1 + j2++] = boardRotate[i][j];
                    continue;
                }
                if (boardRotate[i][j] == PLUS || boardRotate[i][j] == o || boardRotate[i][j] == x) {
                    boardRotateDisappear[i + 1][1 + j2++] = boardRotate[i][j];
                    continue;
                }
            }
            for (; j2 < N; j2++) {
                boardRotateDisappear[i + 1][1 + j2] = WALL;
            }
        }
     
        private static final int[] dr = new int[] { -1, 0, 0, 1, };
        private static final int[] dc = new int[] { 0, -1, 1, 0, };
     
        int[][] used = new int[N][N];
        int countCalculateScore = 0;
     
        private int calculateScore(int[][] boardRotateDisappear) {
            countCalculateScore++;
     
            int scoreO = 0;
            int scoreX = 0;
            LinkedList queue = new LinkedList<>();
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (used[r][c] == countCalculateScore) {
                        continue;
                    }
     
                    if (boardRotateDisappear[r][c] == o || boardRotateDisappear[r][c] == x) {
     
                    } else {
                        continue;
                    }
     
                    queue.add((1 << 16) | (r << 8) | c);
                    used[r][c] = countCalculateScore;
     
                    for (; !queue.isEmpty();) {
                        int v = queue.pollFirst();
                        int count = (v >>> 16) & ((1 << 16) - 1);
                        int r2 = (v >>> 8) & 255;
                        int c2 = v & 255;
     
                        if (boardRotateDisappear[r2][c2] == o) {
                            scoreO = Math.max(scoreO, count);
                        }
                        if (boardRotateDisappear[r2][c2] == x) {
                            scoreX = Math.max(scoreX, count);
                        }
     
                        for (int d = 0; d < dr.length; d++) {
                            int nextR = r2 + dr[d];
                            int nextC = c2 + dc[d];
     
                            if (nextR < 0 || nextR >= N) {
                                continue;
                            }
                            if (nextC < 0 || nextC >= N) {
                                continue;
                            }
                            if (used[nextR][nextC] == countCalculateScore) {
                                continue;
                            }
                            if (boardRotateDisappear[nextR][nextC] != boardRotateDisappear[r2][c2]) {
                                continue;
                            }
     
                            queue.add(((count + 1) << 16) | (nextR << 8) | nextC);
                            used[nextR][nextC] = countCalculateScore;
                        }
                    }
                }
            }
            return scoreO + scoreX;
        }
     
        private boolean SAaccept(double temperature, double score, double newScore) {
            boolean accept = RNG.nextDouble() < StrictMath.exp(-(score - newScore) / temperature);
            return accept;
        }
     
        private static final boolean useTime = true;
     
        private double startTime = 0;
        private double endTime = 10.0 * 0.95;
        private double time = startTime;
     
        private double startTemperature = 3.15;
        private static final double endTemperature = 0;
        private double temperature = startTemperature;
     
        private int loop = 0;
        private int change;
        private int ac;
     
        private static final int mask = (1 << 10) - 1;
     
        private boolean isTimeover() {
            if ((loop & mask) != 0) {
                return false;
            }
     
            time = useTime ? TIME_MANAGER.getSecond() : loop;
     
            if (time >= endTime) {
                return true;
            }
     
            temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
     
            if ((loop & mask) != 0) {
            } else {
                Utils.debug(String.format("loop, %8d, change, %5.2f, AC, %5.2f, temperature, %5.2f, score, %10d, time, %s", loop, 100.0 * change / loop, 100.0 * ac / change, temperature, score, TIME_MANAGER.getSecondString()));
            }
     
            return false;
        }
     
    }
     
    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);
        }
     
    }
     
    class IntArray {
        public int[] values;
        public int length;
     
        public IntArray() {
            this(new int[4], 0);
        }
     
        public IntArray(int capacity) {
            this(new int[capacity], 0);
        }
     
        public IntArray(int[] values) {
            this(values, values.length);
        }
     
        public IntArray(int[] values, int length) {
            this.values = values;
            this.length = length;
        }
     
        public void add(int value) {
            if (length == values.length) {
                values = Arrays.copyOf(values, values.length << 1);
            }
            values[length++] = value;
        }
     
        public int remove() {
            return values[--length];
        }
     
        public boolean contains(int value) {
            for (int i = 0; i < length; i++) {
                if (values[i] == value) {
                    return true;
                }
            }
            return false;
        }
     
        public void clear() {
            length = 0;
        }
     
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("{");
            for (int i = 0; i < length; i++) {
                sb.append(values[i] + ",");
            }
            sb.append("}");
            return sb.toString();
        }
     
        public boolean isEmpty() {
            return length == 0;
        }
     
        public int remove(int index) {
            if (index >= length) {
                throw new AssertionError();
            }
     
            if (index == length - 1) {
                return remove();
            }
     
            int res = values[index];
            System.arraycopy(values, index + 1, values, index, length - (index + 1));
            length--;
     
            return res;
        }
     
        public void set(int index, int value) {
            if (index >= length) {
                throw new AssertionError();
            }
     
            if (length >= values.length - 1) {
                values = Arrays.copyOf(values, values.length << 1);
            }
            System.arraycopy(values, index, values, index + 1, length - index);
            length++;
     
            values[index] = value;
        }
     
        public IntArray copy() {
            return new IntArray(Arrays.copyOf(values, length), length);
        }
     
        public int[] toArray() {
            return Arrays.copyOf(values, length);
        }
     
    }
     
    class TimeManager {
        private long start;
        private int count;
     
        public TimeManager() {
            init();
        }
     
        public int getCount() {
            return count;
        }
     
        public double getSecond() {
            count++;
            return (System.nanoTime() - start) * 1e-9;
        }
     
        public long getTime() {
            count++;
            return System.nanoTime() - start;
        }
     
        public void init() {
            init(System.nanoTime());
        }
     
        public void init(long start) {
            this.start = start;
            count = 0;
        }
     
        public String toString() {
            return toString(getSecond());
        }
     
        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 XorShift {
        private static final double toDouble = 1.0 / 2147483648.0;
        private int w = 88675123;
        private int x = 123456789;
        private int y = 362436069;
        private int z = 521288629;
        private int count = 0;
     
        public XorShift() {
            x = (int) System.nanoTime();
        }
     
        public XorShift(long l) {
            x = (int) l;
        }
     
        public int getCount() {
            return count;
        }
     
        public double nextDouble() {
            return (nextInt() & Integer.MAX_VALUE) * toDouble;
        }
     
        public int nextInt() {
            count++;
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
            return w;
        }
     
        public int nextInt(int n) {
            return (int) (n * nextDouble());
        }
     
        public long nextLong() {
            long a = nextInt();
            long b = nextInt();
            return (a << 32) ^ b;
        }
     
    }

このページのトップヘ