EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

October 2018



Approach 注文の量を各アイテムごとに計算する。量は、max(全てのアイテムの平均 + 係数 * 全てのアイテムの標準偏差, sqrt(min(期限の上限, 期限)) * 平均 + 係数 * 標準偏差) - 在庫。もし売値が買値より小さければ、量を 0.5 * (売値-買値) 減らす。ここで、係数は day が 1 から 100 に変化するとき、 3 から 0  に線形に変化する。期限の上限は day が 1 から 100 に変化するとき、 3 から 1  に線形に変化する。

後3%なんだったんだろう?


source code

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class ProductInventory {
private int day = 0;
private int[] buyPrice;
private int[] sellPrice;
private int[] expires;
private int numItems;
private int[][] stock;

private MeanHelper[] helpers;
private MeanHelper helpersAll;

public int init(int[] buy, int[] sell, int[] expiration) {
numItems = buy.length;
buyPrice = buy;
sellPrice = sell;
expires = expiration;

Utils.debug("numItems", numItems);
Utils.debug("buy", buy);
Utils.debug("sell", sell);
Utils.debug("expiration", expiration);

stock = new int[16][numItems];

helpers = new MeanHelper[numItems];
for (int i = 0; i < numItems; i++) {
helpers[i] = new MeanHelper();
}
helpersAll = new MeanHelper();

return 0;
}

public int[] order(int[] yesterday) {

int[] copyYesterday = Arrays.copyOf(yesterday, numItems);

for (int i = 0; i < numItems; i++) {
if (copyYesterday[i] == 0) {
continue;
}
for (int d = 0; d < 16; d++) {
while (copyYesterday[i] > 0 && stock[d][i] > 0) {
stock[d][i]--;
copyYesterday[i]--;
}
}
if (day > 0 && copyYesterday[i] > 0) {
Utils.debug(copyYesterday[i]);
}
}

for (int i = 0; i < numItems; i++) {
for (int d = 0; d < 15; d++) {
stock[d][i] = stock[d + 1][i];
}
stock[15][i] = 0;
}
day++;

if (day == 1) {
copyYesterday = Arrays.copyOf(yesterday, numItems);
for (int i = 0; i < numItems; i++) {
int[] day10 = new int[10];

for (int d = 0; copyYesterday[i]-- > 0; d = (d + 1) % 10) {
day10[d]++;
}

for (int d = 0; d < 10; d++) {
helpers[i].add(day10[d]);
helpersAll.add(day10[d]);
}
}
} else {
for (int i = 0; i < numItems; i++) {
helpers[i].add(yesterday[i]);
helpersAll.add(yesterday[i]);
}
}

double[] means = new double[numItems];
for (int i = 0; i < numItems; i++) {
means[i] = helpers[i].mean(0);
}

double[] sds = new double[numItems];
for (int i = 0; i < numItems; i++) {
sds[i] = helpers[i].standardDeviation(0);
}

double meanAllItem = helpersAll.mean(0);
double sdAllItem = helpersAll.standardDeviation(0);

int[] sumStocks = new int[numItems];
for (int d = 0; d < 16; d++) {
for (int i = 0; i < numItems; i++) {
sumStocks[i] += stock[d][i];
}
}

double coefSD = 3.0 + (0.0 - 3.0) * (day / 100.0);
double coefSDAll = 3.0 + (0.0 - 3.0) * (day / 100.0);
double coefExpi = 3.0 + (1.0 - 3.0) * (day / 100.0);

int[] orders = new int[numItems];
for (int i = 0; i < numItems; i++) {
double d = Math.max(meanAllItem + coefSDAll * sdAllItem, Math.sqrt(Math.min(coefExpi, expires[i])) * means[i] + coefSD * sds[i]) - sumStocks[i];
if (sellPrice[i] - buyPrice[i] < 0) {
d += 0.5 * (sellPrice[i] - buyPrice[i]);
}
d = Math.round(d);
d = Math.min(100, Math.max(0, d));
if (d > 0) {
orders[i] += (int) d;
}
}
for (int i = 0; i < numItems; i++) {
stock[expires[i]][i] += orders[i];
}
return orders;
}

public static void main(String[] args) throws IOException {
int n;
int[] buy;
int[] sell;
int[] expiration;
int[] yesterday;
int[] res;

try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
n = Integer.parseInt(in.readLine());
buy = new int[n];
for (int i = 0; i < n; i++) {
buy[i] = Integer.parseInt(in.readLine());
}

n = Integer.parseInt(in.readLine());
sell = new int[n];
for (int i = 0; i < n; i++) {
sell[i] = Integer.parseInt(in.readLine());
}

n = Integer.parseInt(in.readLine());
expiration = new int[n];
for (int i = 0; i < n; i++) {
expiration[i] = Integer.parseInt(in.readLine());
}

ProductInventory sol = new ProductInventory();
System.out.printf("%d\n", sol.init(buy, sell, expiration));
System.out.flush();

for (int k = 0; k < 100; k++) {
n = Integer.parseInt(in.readLine());
yesterday = new int[n];
for (int i = 0; i < n; i++) {
yesterday[i] = Integer.parseInt(in.readLine());
}

res = sol.order(yesterday);

System.out.printf("%d\n", res.length);
for (int i = 0; i < res.length; i++) {
System.out.printf("%d\n", res[i]);
}
System.out.flush();
}
}
}
}

class MeanHelper {
private double max;
private double min;
private double sum;
private double sumSquared;
private double sumCubed;
private double sumFourth;
private int count;

public MeanHelper() {
clear();
}

public void add(double value) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value;
double valueSquared = value * value;
sumSquared += valueSquared;
sumCubed += valueSquared * value;
sumFourth += valueSquared * valueSquared;
count++;
}

public void add(double value, double number) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value * number;
double valueSquared = value * value;
sumSquared += valueSquared * number;
sumCubed += valueSquared * value * number;
sumFourth += valueSquared * valueSquared * number;
count += number;
}

public double kurtosis(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
}

public double skewness(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
}

public double mean() {
if (isEmpty()) {
throw new AssertionError();
}
return sum / count;
}

public double mean(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sum / count;
}

public double sumOfSquaredError() {
if (isEmpty()) {
throw new AssertionError();
}
return sumSquared - sum * sum / count;
}

public double sumOfSquaredError(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sumSquared - sum * sum / count;
}

public double variance() {
if (isEmpty()) {
throw new AssertionError();
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double variance(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double unbiasedVariance() {
if (count - 1 == 0) {
throw new AssertionError();
}
return (count * variance()) / (count - 1);
}

private double unbiasedVariance(double defaultValue) {
if (count - 1 == 0) {
return defaultValue;
}
return (count * variance()) / (count - 1);
}

public double standardDeviation() {
return Math.sqrt(variance());
}

public double standardDeviation(double defaultValue) {
return Math.sqrt(variance(defaultValue));
}

public double unbiasedStandardDeviation() {
return Math.sqrt(unbiasedVariance());
}

public double unbiasedStandardDeviation(double defaultValue) {
return Math.sqrt(unbiasedVariance(defaultValue));
}

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

public void clear() {
max = Double.NEGATIVE_INFINITY;
min = Double.POSITIVE_INFINITY;
sum = 0;
sumSquared = 0;
sumCubed = 0;
sumFourth = 0;
count = 0;
}

public double max() {
if (isEmpty()) {
throw new AssertionError();
}
return max;
}

public double max(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return max;
}

public double min() {
if (isEmpty()) {
throw new AssertionError();
}
return min;
}

public double min(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return min;
}

public int count() {
return count;
}

public double sum() {
return sum;
}

public double sumSquared() {
return sumSquared;
}
}

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

}



Result  Grid Graph の Widest Improvement と Deepest Improvement を運良く受賞してた。Widest Improvement は、Nakano さんがグラフファイルを公開してなかったら、受賞してなかった。かけている時間が違うのか、使っているマシンの数または計算力が違うのか、 Nakano さんの数字とは差があった。Deepest Improvement も、サイズの一番小さいグラフが、10ケースの中で Deepest だったというだけだった。


Approach 焼きなまし法を使いました。

  • スコア : average shortest path length(ASPL)
  • 近傍は、4つのつながったノードの、ノード1とノード2の間の辺とノード3とノード4の間の辺を削除して、ノード1とノード3の間とノード2とノード4の間に辺を作る。
  • 時間 : 10分
  • 温度 : 低温
  • 10回再スタートするたびに線形に開始温度を下げる。
  • 4コアのマシンを使っているので、4プロセス並行で焼き鈍した。
  • Nakano さんのグラフを改善したときは、これを2週間続けた。

sa




source code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

public class Main {
private int R;
private int C;
private int length;
private int degree;

private double[] startTemperatures = { 0.001, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001, 0.0001, };
private int[] gridR = { 4, 32, 32, 32, 16, 16, 16, 4, 4, 4, };
private int[] gridC = { 16, 32, 32, 32, 64, 64, 64, 256, 256, 256, };
private int[] degrees = { 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, };
private int[] lengthes = { 4, 3, 4, 5, 4, 5, 7, 12, 18, 24, };

private ArrayList<IntSet> graph;
private ArrayList<IntSet> bestGraph;

private int diam;
private int bestDiam;

private double aspl;
private double bestAspl;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();

private ArrayList<Integer> dr;
private ArrayList<Integer> dc;

private boolean[] used;

public static void main(String[] args) {
new Main().run();
}

private void run() {
for (int i = 0; i < gridR.length; i++) {
for (double j = 1; j > 1e-9; j -= 0.1) {
R = gridR[i];
C = gridC[i];
degree = degrees[i];
length = lengthes[i];
Utils.debug(R + "x" + C, "degree", degree, "length", length);

init();
bestDiam = (int) 1e9;
bestAspl = 1e9;
readSolution();
printDegree();
Utils.debug(bestDiam, bestAspl);
sa.startTime = watch.getSecond();
sa.endTime = sa.startTime + 1 * 10 * 60;
sa.startTemperature = startTemperatures[i] * j;
sa.endTemperature = 0;
sa.expTemperature = 1;
SA();

writeSolution();
}
}
}

private void writeSolution() {
StringBuilder sb = new StringBuilder();
for (int from = 0; from < R * C; from++) {
for (int j = 0; j < graph.get(from).size(); j++) {
int to = graph.get(from).get(j);
if (from < to) {
sb.append((r(from) + "," + c(from)) + " " + (r(to) + "," + c(to)) + "\n");
}
}
}
TextFileIO.write(sb.toString(), new File("./out/grid_" + (R + "_x_" + C) + "_d_" + degree + "_l_" + length + "_diam_" + diam + "_aspl_" + aspl + "_.edges"));
}

private void readSolution() {
File outDir = new File("./out/");
for (File file : outDir.listFiles()) {
if (!file.isFile()) {
Utils.debug("continue !file.isFile()");
continue;
}
String name = file.getName();
Utils.debug("name", name);
String[] split = name.split("_");
if (split.length != 13) {
Utils.debug("continue split.length != 13");
continue;
}
if (split[0].equals("grid") && split[2].equals("x") && split[4].equals("d") && split[6].equals("l") && split[8].equals("diam") && split[10].equals("aspl")) {
} else {
Utils.debug("continue !(split[0].equals(\"grid\") && split[2].equals(\"x\") && split[4].equals(\"d\") && split[6].equals(\"l\") && split[8].equals(\"diam\") && split[10].equals(\"aspl\"))");
continue;
}
int r = Integer.parseInt(split[1]);
int c = Integer.parseInt(split[3]);
int d = Integer.parseInt(split[5]);
int l = Integer.parseInt(split[7]);
int diam = Integer.parseInt(split[9]);
double aspl = Double.parseDouble(split[11]);
if (r == this.R && c == this.C && d == this.degree && l == this.length) {
} else {
Utils.debug("continue !(r == this.R && c == this.C && d == this.degree && l == this.length)");
continue;
}
Utils.debug("read " + name);
for (int from = 0; from < R * C; from++) {
graph.get(from).clear();
}
for (String line : TextFileIO.readLines(file)) {
String[] split2 = line.split("[, ]");
int fromR = Integer.parseInt(split2[0]);
int fromC = Integer.parseInt(split2[1]);
int toR = Integer.parseInt(split2[2]);
int toC = Integer.parseInt(split2[3]);
int from = z(fromR, fromC);
int to = z(toR, toC);
graph.get(from).add(to);
graph.get(to).add(from);
}
calculateScore(graph);
saveBest();
loadBest();
calculateScore(graph);
}

}

private void init() {
watch.init();

intQueue = new IntQueue(R * C + 2);
graph = new ArrayList<>();
for (int i = 0; i < R * C; i++) {
graph.add(new IntSet(R * C));
}

bestGraph = new ArrayList<>();
for (int i = 0; i < R * C; i++) {
bestGraph.add(new IntSet(R * C));
}

this.dr = new ArrayList<>();
this.dc = new ArrayList<>();
for (int dr = -length; dr <= length; dr++) {
int l = length - Math.abs(dr);
for (int dc = -l; dc <= l; dc++) {
if (dr == 0 && dc == 0) {
continue;
}
this.dr.add(dr);
this.dc.add(dc);
}
}
used = new boolean[R * C];

Utils.debug("init", "time", watch.getSecondString());
}

private void greedy() {
for (int i = 0; i < R * C; i++) {
graph.get(i).clear();
}

for (int d = 0; d < degree; d++) {
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
int from = r * C + c;
if (graph.get(from).size() > d) {
continue;
}
int min = (int) 1e9;
int minDistance = (int) 1e9;
IntSet toSet = new IntSet(R * C);

for (int r2 = 0; r2 < R; r2++) {
for (int c2 = 0; c2 < C; c2++) {
int nextR = r2;
int nextC = c2;
if (nextR < 0 || nextR >= R) {
continue;
}
if (nextC < 0 || nextC >= C) {
continue;
}
int to = nextR * C + nextC;
if (to == from) {
continue;
}
if (graph.get(from).contains(to)) {
continue;
}
if (graph.get(to).size() > d) {
continue;
}

boolean useSizeAndDistance = true;
if (useSizeAndDistance) {

int distance = Math.abs(nextR - r) + Math.abs(nextC - c);
if (distance <= length) {
distance = -distance;
}
if (graph.get(to).size() < min || (graph.get(to).size() == min && distance < minDistance)) {
min = graph.get(to).size();
minDistance = distance;
toSet.clear();
toSet.add(to);
} else if (graph.get(to).size() == min && distance == minDistance) {
toSet.add(to);
}
}

boolean useSize = !true;
if (useSize) {

if (graph.get(to).size() < min) {
min = graph.get(to).size();
toSet.clear();
toSet.add(to);
} else if (graph.get(to).size() == min) {
toSet.add(to);
}
}

boolean useDistance = !true;
if (useDistance) {
int distance = Math.abs(nextR - r) + Math.abs(nextC - c);
if (distance < min) {
min = distance;
toSet.clear();
toSet.add(to);
} else if (distance == min) {
toSet.add(to);
}
}
}
}

if (toSet.isEmpty()) {
Utils.debug("minToSet.isEmpty()", "d", d, "r", r, "c", c);
continue;
}

int to = toSet.get((int) (toSet.size() * rng.nextDouble()));
assert min == graph.get(to).size();
graph.get(from).add(to);
graph.get(to).add(from);
assert graph.get(from).size() <= degree;
assert graph.get(to).size() <= degree;

}
}
}
}

private void addEdge() {
ArrayList<Integer> nodes = new ArrayList<>();
for (int i = 0; i < R * C; i++) {
if (graph.get(i).size() < degree) {
nodes.add(i);
}
}

boolean add = false;
for (int i = 0; i < nodes.size(); i++) {
int node = nodes.get(i).intValue();
if (graph.get(node).size() >= degree) {
continue;
}
for (int j = i + 1; j < nodes.size(); j++) {
int node2 = nodes.get(j).intValue();
if (graph.get(node).size() >= degree) {
continue;
}
if (graph.get(node2).size() >= degree) {
continue;
}
if (graph.get(node).contains(node2)) {
continue;
}

graph.get(node).add(node2);
graph.get(node2).add(node);
add = true;
}
}

if (add) {
Utils.debug("addEdge()");
}
}

private void random() {
ArrayList<Integer> vertexes = new ArrayList<>();
for (int node = 0; node < R * C; node++) {
for (int degree = 0; degree < this.degree; degree++) {
vertexes.add(node);
}
}
Collections.shuffle(vertexes);

for (int i = 0; i < vertexes.size(); i += 2) {
int from = vertexes.get(i + 0).intValue();
int to = vertexes.get(i + 1).intValue();
graph.get(from).add(to);
graph.get(to).add(from);
}
}

private void SA() {
double second = Math.ceil(watch.getSecond());
sa.init();
for (;; sa.numIterations++) {
if ((sa.numIterations & ((1 << 0) - 1)) == 0) {
sa.update();

if (sa.isTLE() || sa.numIterations > 1e5 + sa.lastAcceptIterations) {
loadBest();
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", invalid), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
if (watch.getSecond() > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", invalid), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutate();
}
Utils.debug("SA", "time", watch.getSecondString());
}

private void invalidToValidSA() {
IntSet invalid = new IntSet(R * C * R * C);
for (int node = 0; node < R * C; node++) {
for (int i = 0; i < graph.get(node).size(); i++) {
int nextNode = graph.get(node).get(i);
if (length(node, nextNode) > length) {
invalid.add(Math.min(node, nextNode) * (R * C) + Math.max(node, nextNode));
}
}
}
if (invalid.size() == 0) {
return;
}

double second = Math.ceil(watch.getSecond());
sa.init();
for (;; sa.numIterations++) {
if ((sa.numIterations & ((1 << 0) - 1)) == 0) {
sa.update();

if (sa.isTLE() || sa.numIterations > 1e5 + sa.lastAcceptIterations) {
loadBest();
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", invalid), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}
if (watch.getSecond() > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%2d", invalid), String.format("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}
int v = invalid.get((int) (invalid.size() * rng.nextDouble()));
int node1 = v / (R * C);
int node2 = v % (R * C);
int node = rng.nextDouble() < 0.5 ? node1 : node2;

}
Utils.debug("invalidToValidSA", "time", watch.getSecondString());
}

private void mutate() {
swapNextAndNextNext();
}

private void mutate2() {
double random = 2 * rng.nextDouble();
if (random < 1) {
swap2();
} else if (random < 2) {
swapNextAndNextNext();
}
}

private void swap2() {
int from = (int) (R * C * rng.nextDouble());
assert graph.get(from).size() <= degree : Utils.toString("graph.get(" + from + ").size()", graph.get(from).size());
int fromR = r(from);
int fromC = c(from);

int index0 = (int) (dr.size() * rng.nextDouble());
int to2R = fromR + dr.get(index0).intValue();
int to2C = fromC + dc.get(index0).intValue();
int to2 = z(to2R, to2C);
assert to2 != from;
while (!isValid(to2R, 0, R) || !isValid(to2C, 0, C)) {
index0 = (int) (dr.size() * rng.nextDouble());
to2R = fromR + dr.get(index0).intValue();
to2C = fromC + dc.get(index0).intValue();
to2 = z(to2R, to2C);
}
if (graph.get(from).contains(to2)) {
return;
}
int from2 = graph.get(to2).get((int) (graph.get(to2).size() * rng.nextDouble()));
assert from2 != from;
int index = (int) (graph.get(from).size() * rng.nextDouble());
int to = graph.get(from).get(index);
if (from2 == to || graph.get(from2).contains(to)) {
return;
}
if (graph.get(from).contains(to2)) {
return;
}
if (graph.get(from2).contains(to)) {
return;
}
if (graph.get(to2).contains(from)) {
return;
}
if (graph.get(to).contains(from2)) {
return;
}

graph.get(from).remove(graph.get(from).indexOf(to));
graph.get(from2).remove(graph.get(from2).indexOf(to2));
graph.get(from).add(to2);
graph.get(from2).add(to);

graph.get(to).remove(graph.get(to).indexOf(from));
graph.get(to2).remove(graph.get(to2).indexOf(from2));
graph.get(to).add(from2);
graph.get(to2).add(from);
int currentDiam = diam;
double currentAspl = aspl;
int currentInvalid = invalid;

calculateScore(graph);
double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

if (sa.accept(deltaScore)) {
saveBest();
} else {

diam = currentDiam;
aspl = currentAspl;
invalid = currentInvalid;

graph.get(from).remove(graph.get(from).indexOf(to2));
graph.get(from2).remove(graph.get(from2).indexOf(to));
graph.get(from).add(to);
graph.get(from2).add(to2);

graph.get(to).remove(graph.get(to).indexOf(from2));
graph.get(to2).remove(graph.get(to2).indexOf(from));
graph.get(to).add(from);
graph.get(to2).add(from2);

}
}

private void printDegree() {
for (int i = 0; i < R * C; i++) {
if (graph.get(i).size() != degree) {
Utils.debug("ac", sa.acceptIterations, "node", i, "degree", graph.get(i).size(), "max degree", degree);
}
}
}

private void swapNextAndNextNext() {
int node0 = (int) (R * C * rng.nextDouble());
int node1 = graph.get(node0).get((int) (graph.get(node0).size() * rng.nextDouble()));
assert node1 != node0;
int node2 = graph.get(node1).get((int) (graph.get(node1).size() * rng.nextDouble()));
while (node2 == node0) {
node2 = graph.get(node1).get((int) (graph.get(node1).size() * rng.nextDouble()));
}
int node3 = graph.get(node2).get((int) (graph.get(node2).size() * rng.nextDouble()));
while (node3 == node1) {
node3 = graph.get(node2).get((int) (graph.get(node2).size() * rng.nextDouble()));
}
if (graph.get(node0).contains(node2)) {
return;
}
if (graph.get(node1).contains(node3)) {
return;
}
if (graph.get(node2).contains(node0)) {
return;
}
if (graph.get(node3).contains(node1)) {
return;
}

if (length(node0, node2) > length) {
return;
}
if (length(node1, node3) > length) {
return;
}

graph.get(node0).remove(graph.get(node0).indexOf(node1));
graph.get(node0).add(node2);

graph.get(node1).remove(graph.get(node1).indexOf(node0));
graph.get(node1).add(node3);

graph.get(node2).remove(graph.get(node2).indexOf(node3));
graph.get(node2).add(node0);

graph.get(node3).remove(graph.get(node3).indexOf(node2));
graph.get(node3).add(node1);

int currentDiam = diam;
double currentAspl = aspl;
int currentInvalid = invalid;

calculateScore(graph);
double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

if (sa.accept(deltaScore)) {
saveBest();
} else {
diam = currentDiam;
aspl = currentAspl;
invalid = currentInvalid;

graph.get(node0).remove(graph.get(node0).indexOf(node2));
graph.get(node0).add(node1);

graph.get(node1).remove(graph.get(node1).indexOf(node3));
graph.get(node1).add(node0);

graph.get(node2).remove(graph.get(node2).indexOf(node0));
graph.get(node2).add(node3);

graph.get(node3).remove(graph.get(node3).indexOf(node1));
graph.get(node3).add(node2);

}
}

private int length(int z, int z2) {
return Math.abs(r(z2) - r(z)) + Math.abs(c(z2) - c(z));
}

private boolean isValid(int v, int min, int minUpper) {
return v >= min && v < minUpper;
}

private IntQueue intQueue;

boolean print = !true;
private int invalid;

private void calculateScore(ArrayList<IntSet> graph) {
int max = 0;
int sum = 0;
int invalid = 0;
IntQueue queue = this.intQueue;
for (int node = 0; node < R * C; node++) {

queue.clear();
Arrays.fill(used, false);
{
queue.add((0 << 16) | (node));
used[node] = true;
}
for (; !queue.isEmpty();) {
int v = queue.poll();
int distance = (v >>> 16) & ((1 << 16) - 1);
int currentNode = (v >>> 0) & ((1 << 16) - 1);
int r = r(currentNode);
int c = c(currentNode);

if (print && distance == 5) {
Utils.debug(node / C, node % C, r, c);
}

if (distance > 0) {
max = Math.max(max, distance);
sum += distance;
}

for (int i = 0; i < graph.get(currentNode).size(); i++) {
int nextNode = graph.get(currentNode).get(i);
if (used[nextNode]) {
continue;
}

int nextR = r(nextNode);
int nextC = c(nextNode);
if (Math.abs(nextR - r) + Math.abs(nextC - c) > length) {
invalid++;
}
used[nextNode] = true;
queue.add(((distance + 1) << 16) | (nextNode));
}
}

}
aspl = (double) sum / (R * C * R * C - R * C);
diam = max;
this.invalid = invalid;
}

private void saveBest() {
if (invalid > 0) {
Utils.debug("invalid", invalid);
return;
}
if (diam < bestDiam || (diam == bestDiam && aspl < bestAspl)) {
bestDiam = diam;
bestAspl = aspl;
for (int node = 0; node < R * C; node++) {
bestGraph.get(node).clear();
for (int i = 0; i < graph.get(node).size(); i++) {
bestGraph.get(node).add(graph.get(node).get(i));
}
}

}
}

private void loadBest() {
diam = bestDiam;
aspl = bestAspl;
for (int node = 0; node < R * C; node++) {
graph.get(node).clear();
for (int i = 0; i < bestGraph.get(node).size(); i++) {
graph.get(node).add(bestGraph.get(node).get(i));
}
}
}

private int z(int r, int c) {
return r * C + c;
}

private int r(int z) {
return z / C;
}

private int c(int z) {
return z % C;
}
}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1e6;
public double time = startTime;

public double startTemperature = 40;
public double endTemperature = 0;
public double expTemperature = 1;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 101;
public double endRange = 3;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;
public int lastAcceptIterations;

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? Main.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? Main.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++;
lastAcceptIterations = numIterations;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
lastAcceptIterations = numIterations;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
lastAcceptIterations = numIterations;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
lastAcceptIterations = numIterations;
return true;
}
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 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 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 UnionFind {
private int[] par;
private int[] rank;

public UnionFind(int capacity) {
par = new int[capacity];
rank = new int[capacity];
}

public void init(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
rank[i] = 0;
}
}

public int getRoot(int x) {
if (par[x] == x) {
return x;
} else {
par[x] = getRoot(par[x]);
return par[x];
}
}

public void unite(int x, int y) {
x = getRoot(x);
y = getRoot(y);
if (x == y) {
return;
}
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) {
rank[x]++;
}
}
}

public boolean isSame(int x, int y) {
return getRoot(x) == getRoot(y);
}
}

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 IntQueue {
private int[] queue;
private int current;
private int size;

public IntQueue(int capacity) {
queue = new int[capacity];
}

public void clear() {
init();
}

public void init() {
current = 0;
size = 0;
}

public boolean isEmpty() {
return current == size;
}

public int poll() {
return queue[current++];
}

public void add(int value) {
queue[size++] = value;
}
}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class TextFileIO {
public static String read0(File file, String encoding) {
StringBuilder sb = new StringBuilder();
BufferedReader reader = null;
try {
reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
char[] ch = new char[50000];
int read;
while ((read = reader.read(ch)) > 0) {
String s = new String(ch, 0, read);
sb.append(s);
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return sb.toString();
}

public static String read(File file) {
return read(file, "UTF-8");
}

public static String read(File file, String encoding) {
StringBuilder sb = new StringBuilder();
BufferedReader reader = null;
try {
reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
for (String line; (line = reader.readLine()) != null;) {
sb.append(line + "\n");
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return sb.toString();
}

public static String[] read2(File file, String encoding) {
ArrayList<String> list = new ArrayList<String>();
BufferedReader reader = null;
try {
reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
for (String line; (line = reader.readLine()) != null;) {
list.add(line);
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return (String[]) list.toArray(new String[list.size()]);
}

public static ArrayList<String> readLines(File file) {
return read3(file, "UTF-8");
}

public static ArrayList<String> readLines(File file, String encoding) {
return read3(file, encoding);
}

public static ArrayList<String> read3(File file) {
return read3(file, "UTF-8");
}

public static ArrayList<String> read3(File file, String encoding) {
ArrayList<String> res = new ArrayList<String>();

try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
for (String line; (line = reader.readLine()) != null;) {
res.add(line);
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return res;
}

public static ArrayList<String> readFirstNLines(int numLines, File file) {
return readFirstNLines(numLines, file, "UTF-8");
}

public static ArrayList<String> readFirstNLines(int numLines, File file, String encoding) {
ArrayList<String> res = new ArrayList<String>();
BufferedReader reader = null;
try {
reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
for (String line; (line = reader.readLine()) != null;) {
res.add(line);
if (res.size() >= numLines) {
break;
}
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (reader != null) {
try {
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
return res;
}

private static void mkParents(File file) {
File parentFile = file.getParentFile();
if (!parentFile.exists()) {
for (int i = 0; i < 5; i++) {
if (parentFile.mkdirs()) {
break;
}
}
}
}

public static void write(String contents, File file, String encoding) {
mkParents(file);

BufferedWriter writer = null;
try {
writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file), encoding));
writer.write(contents);
writer.flush();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (writer != null) {
try {
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}

public static void append(String contents, File file, String encoding) {
mkParents(file);

BufferedWriter writer = null;
try {
writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file, true), encoding));
writer.append(contents);
writer.flush();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (writer != null) {
try {
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}

public static void appendln(String contents, File file, String encoding) {
append(contents + "\n", file, encoding);
}

public static void write(String contents) {
write(contents, new File("./debug.txt"), "UTF-8");
}

public static void write(String contents, File file) {
write(contents, file, "UTF-8");
}

public static void writeln(String contents) {
write(contents + "\n", new File("./debug.txt"), "UTF-8");
}

public static void writeln(String contents, File file) {
write(contents + "\n", file, "UTF-8");
}

public static void append(String contents) {
append(contents, new File("./debug.txt"), "UTF-8");
}

public static void append(String contents, File file) {
append(contents, file, "UTF-8");
}

public static void appendln(String contents) {
append(contents + "\n", new File("./debug.txt"), "UTF-8");
}

public static void appendln(String contents, File file) {
append(contents + "\n", file, "UTF-8");
}

public static String read() {
return read(new File("./debug.txt"), "UTF-8");
}

public static int calculateNumLines(File file) {
return calculateNumLines(file, "UTF-8");
}

public static int calculateNumLines(File file, String encoding) {
int numLines = 0;
try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
for (String line; (line = reader.readLine()) != null;) {
numLines++;
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
return numLines;
}

public static void printRandomLines(double d, File file) {
printRandomLines(d, file, "UTF-8");
}

public static void printRandomLines(double d, File file, String encoding) {
Random rng = new Random(System.nanoTime());
try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
for (String line; (line = reader.readLine()) != null;) {
if (rng.nextDouble() < d) {
Utils.debug(line);
}
}
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}

}



↑このページのトップヘ