Approach ヤマトコンで755XXXXがでた後に1日参加しました。焼きなまし法を使いました。スコアの差をO(NxN), 状態の更新をO(NxN) でやってコーディングフェーズを終えました。１位の Tomas Rokicki さんによると、スコアの差をO(1), 更新をO( (NxN)^2 ) でできたらしい。他にはフローで割当問題を解くのが有効だったそうな。
実行フェーズは１時間くらい焼きなますのを何回かやった。N<=12は最適解だった。
差 : O(1) をやってみたけど、なんか遅いので計算量を...
- iteration の平均計算量
- N=10, 受理率10%
- 差 : O(NxN), 更新 : O(NxN)
iteration の平均計算量 = O( NxN + 0.1 x NxN ) = O( 100 + 0.1 x 100 ) = O( 110 ) - 差 : O(1), 更新 : O( (NxN)^2 )
iteration の平均計算量 = O( 1 + 0.1 x (NxN)^2 ) = O( 1 + 0.1 x 10000 ) = O( 1001 ) - N=10, 受理率1%
- 差 : O(NxN), 更新 : O(NxN)
iteration の平均計算量 = O( NxN + 0.01 x NxN ) = O( 100 + 0.01 x 100 ) = O( 101 ) - 差 : O(1), 更新 : O( (NxN)^2 )
iteration の平均計算量 = O( 1 + 0.01 x (NxN)^2 ) = O( 1 + 0.01 x 10000 ) = O( 101 ) - N=30, 受理率10%
- 差 : O(NxN), 更新 : O(NxN)
iteration の平均計算量 = O( NxN + 0.1 x NxN ) = O( 900 + 0.1 x 900 ) = O( 990 ) - 差 : O(1), 更新 : O( (NxN)^2 )
iteration の平均計算量 = O( 1 + 0.1 x (NxN)^2 ) = O( 1 + 0.1 x 810000 ) = O( 81001 ) - N=30, 受理率1%
- 差 : O(NxN), 更新 : O(NxN)
iteration の平均計算量 = O( NxN + 0.01 x NxN ) = O( 900 + 0.01 x 900 ) = O( 909 ) - 差 : O(1), 更新 : O( (NxN)^2 )
iteration の平均計算量 = O( 1 + 0.01 x (NxN)^2 ) = O( 1 + 0.01 x 810000 ) = O( 8101 )
source code(差:O(1))
import java.util.Arrays;
public class Main {
private static final long[] lowerBound = new long[] { 0, 0, 10, 72, 816, 3800, 16902, 52528, 155840, 381672, 902550, 1883244, 3813912, 7103408, 12958148, 22225500, 3747816, 60291180, 95730984, 146469252, 221736200, 325763172, 474261920, 673706892, 949783680, 1311600000, 1799572164, 2425939956L, 3252444776L, 4294801980L, 5643997650L };
private int N;
private int NxN;
private IntSet rearrangement;
private IntSet bestRearrangement;
private long score;
private long bestScore = (long) 1e18;
private long[][] indexAndValueToPartScores;
static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());
private SAState sa = new SAState();
public static void main(String[] args) {
new Main().run();
}
private void run() {
init();
solve();
write();
}
private void init() {
N = 6;
NxN = N * N;
rearrangement = new IntSet(NxN);
for (int i = 0; i < NxN; i++) {
rearrangement.add(i);
}
score = calculateScore();
bestScore = (long) 1e18;
bestRearrangement = new IntSet(NxN);
saveBest();
indexAndValueToPartScores = new long[NxN][NxN];
calculateIndexAndValueToPartScores();
watch.init();
}
private void calculateIndexAndValueToPartScores() {
for (int index = 0; index < NxN; index++) {
for (int value = 0; value < NxN; value++) {
int index2 = rearrangement.indexOf(value);
rearrangement.swap(index, index2);
indexAndValueToPartScores[index][value] = calculatePartScore(value);
rearrangement.swap(index, index2);
}
}
}
private void updateIndexAndValueToPartScores(int value1, int value2, int coef) {
for (int index = 0; index < NxN; index++) {
for (int value = 0; value < NxN; value++) {
int index2 = rearrangement.indexOf(value);
rearrangement.swap(index, index2);
indexAndValueToPartScores[index][value] += coef * partScore(value, value1, rearrangement);
indexAndValueToPartScores[index][value] += coef * partScore(value, value2, rearrangement);
rearrangement.swap(index, index2);
}
}
}
private void solve() {
SA();
}
private void SA() {
double second = Math.ceil(watch.getSecond());
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
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("%d", score), String.format("%d", bestScore), 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("%d", score), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}
mutate();
}
Utils.debug("SA", "score", score, "time", watch.getSecondString());
}
private void mutate() {
swap();
}
private void swap() {
int index = (int) (NxN * rng.nextDouble());
int index2 = index;
while (index2 == index) {
index2 = (int) (NxN * rng.nextDouble());
}
int value = rearrangement.get(index);
int value2 = rearrangement.get(index2);
long currentPartScore = indexAndValueToPartScores[index][value];
long currentPartScore2 = indexAndValueToPartScores[index2][value2];
long newPartScore = indexAndValueToPartScores[index2][value];
long newPartScore2 = indexAndValueToPartScores[index][value2];
long deltaScore = (newPartScore - currentPartScore) + (newPartScore2 - currentPartScore2);
if (sa.accept(deltaScore)) {
score += deltaScore;
rearrangement.swap(index, index2);
saveBest();
rearrangement.swap(index, index2);
updateIndexAndValueToPartScores(value, value2, -1);
rearrangement.swap(index, index2);
updateIndexAndValueToPartScores(value, value2, 1);
for (int index3 = 0; index3 < NxN; index3++) {
{
int index4 = rearrangement.indexOf(value);
rearrangement.swap(index3, index4);
indexAndValueToPartScores[index3][value] = calculatePartScore(value);
rearrangement.swap(index3, index4);
}
{
int index4 = rearrangement.indexOf(value2);
rearrangement.swap(index3, index4);
indexAndValueToPartScores[index3][value2] = calculatePartScore(value2);
rearrangement.swap(index3, index4);
}
}
}
}
private long calculateScore() {
long sum = -lowerBound[N];
for (int value = 0; value < NxN; value++) {
for (int value2 = value + 1; value2 < NxN; value2++) {
sum += partScore(value, value2, rearrangement);
}
}
return sum;
}
private long calculatePartScore(int value) {
long sum = 0;
for (int value2 = 0; value2 < NxN; value2++) {
sum += partScore(value, value2, rearrangement);
}
return sum;
}
private int partScore(int value, int value2, IntSet rearrangement) {
return distance2(value, value2) * distance2(rearrangement.indexOf(value), rearrangement.indexOf(value2));
}
private int distance2(int index, int index2) {
int r = r(index);
int c = c(index);
int r2 = r(index2);
int c2 = c(index2);
int dr = Math.min(Math.abs(r - r2), N - Math.abs(r - r2));
int dc = Math.min(Math.abs(c - c2), N - Math.abs(c - c2));
return dr * dr + dc * dc;
}
private int r(int v) {
return v / N;
}
private int c(int v) {
return v % N;
}
private void saveBest() {
if (score < bestScore) {
bestScore = score;
bestRearrangement.clear();
for (int i = 0; i < N * N; i++) {
bestRearrangement.add(rearrangement.get(i));
}
}
}
private void loadBest() {
score = bestScore;
rearrangement.clear();
for (int i = 0; i < N * N; i++) {
rearrangement.add(bestRearrangement.get(i));
}
}
private void write() {
boolean print = true;
if (print) {
char[] cs = new char[30];
{
int i = 0;
for (char c = 'A'; c <= 'Z'; c++) {
cs[i++] = c;
}
cs[i++] = '[';
cs[i++] = '\\';
cs[i++] = ']';
cs[i++] = '^';
assert i == 30;
}
StringBuilder sb = new StringBuilder();
for (int r = 0; r < N; r++) {
sb.append("(");
for (int c = 0; c < N; c++) {
if (c > 0) {
sb.append(", ");
}
int token = rearrangement.get(r * N + c);
sb.append(cs[c(token)]).append(cs[r(token)]);
}
sb.append(")");
if (r + 1 < N) {
sb.append(",");
}
sb.append("\n");
}
System.out.println(sb.toString());
System.out.flush();
}
}
}
class SAState {
public static final boolean useTime = !true;
public double startTime = 0;
public double endTime = 1e6;
public double time = startTime;
public double startTemperature = 100;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;
public double startRange = 0;
public double endRange = 0;
public double range = startRange;
public int numIterations;
public int validIterations;
public int acceptIterations;
private double minAbsDeltaScore;
private double maxAbsDeltaScore;
private MeanHelper helper = new MeanHelper();
public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;
minAbsDeltaScore = 1e99;
maxAbsDeltaScore = 1e-99;
helper.clear();
startTime = useTime ? Main.watch.getSecond() : numIterations;
update();
lastAcceptTemperature = inverseTemperature;
}
public void update() {
updateTime();
updateTemperature();
updateRange();
}
public boolean useMean = !true;
public boolean useMax = true;
public double startRate = 0.01;
public double endRate = 0.01;
public boolean useExp = !true;
public void updateStartTemperature() {
if (useMean) {
double d = helper.mean(maxAbsDeltaScore);
d = d > 0 ? d : maxAbsDeltaScore;
startTemperature = (-1.0 * d) / Math.log(startRate);
} else if (useMax) {
startTemperature = 0.1 * (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
} else {
startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
}
}
public void updateEndTemperature() {
endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
}
public void updateTemperature() {
updateStartTemperature();
updateEndTemperature();
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() {
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) {
double abs = Math.abs(deltaScore);
if (abs > 1e-9) {
helper.add(deltaScore);
minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
}
return acceptS(deltaScore);
}
public boolean acceptB(double deltaScore) {
validIterations++;
if (deltaScore > -1e-9) {
acceptIterations++;
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;
return true;
}
return false;
}
public boolean acceptS(double deltaScore) {
validIterations++;
if (deltaScore < 1e-9) {
acceptIterations++;
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;
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 double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}
public int nextInt(int n) {
return (int) (n * nextDouble());
}
}
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 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;
}
public void swap(int index, int index2) {
int value = indexToValue[index];
int value2 = indexToValue[index2];
{
int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;
}
{
int swap = valueToIndex[value];
valueToIndex[value] = valueToIndex[value2];
valueToIndex[value2] = swap;
}
}
}
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;
}
}
コメント