EvbCFfp1XB

problem and my answer.



Approach

ナイトの置く置かないをフリップするSA。
約5億イテレーション。


高速化


各位置のスコアのデルタを覚えておく(事前に計算しておく + 更新した時に再計算する)。


乱数の生成が遅そう+キャッシュのヒット率を考えて、ランダムに位置を選ぶのを止めて、for(int r=0;r<S;r++)for(int c=0;c<S;c++) にした。


TCO16MMR3のtomerunさんのSAの枝刈りを使いました。

@masashinakata 自分はかなりアグレッシブに枝刈り(?)してるのでその違いかも。 普通は return rnd.nextDouble() < exp(-diff/T) とかですが、その前に if (diff/T > 10) return false を挟んでます


SAの exp(-diff/T) を power(2,-diff/T) にした。

exp(-diff/T) = power(e,-diff/T)
ここでeを2にする
rnd.nextDouble() < power(2,-diff/T)
nextDouble()の実装より
(rng.nextInt() & 2147483647) / 2147483648 < power(2,-diff/T)
移項して
(rng.nextInt() & 2147483647) < 2147483648 * power(2,-diff/T)
                                                    = power(2,31) * power(2,-diff/T)
                                                    = power(2,31-diff/T)
-diff/Tを四捨五入して整数に直して、
                                                    ≃  power(2,(int)(31.5+ -diff/T))
                                                    = (1 << (int)(31.5+ -diff/T))






source code

import java.io.BufferedReader;

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

//Example scores:
//0) 23.0
//1) 598.0
//2) 89405.0
//3) 3602.0
//4) 5164.0
//5) 21087.0
//6) 23533.0
//7) 63163.0
//8) 43742.0
//9) 24945.0

public class KnightsAttacks {
private static final int[] knightZ = { z(-2, -1) - z(0, 0), z(-2, 1) - z(0, 0), z(-1, 2) - z(0, 0), z(1, 2) - z(0, 0), z(2, 1) - z(0, 0), z(2, -1) - z(0, 0), z(1, -2) - z(0, 0), z(-1, -2) - z(0, 0), };

private static final byte outside = (byte) 127;

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

private int S;
private static final int SupS = 512;

private static final byte[] attacksExpected = new byte[SupS * SupS];
private static final byte[] attacksActual = new byte[SupS * SupS];

private static final byte[] deltaAdd = new byte[SupS * SupS];
private static final byte[] deltaRemove = new byte[SupS * SupS];

private SAState sa = new SAState();

private int score;
private int bestScore;

private static final boolean[] solution = new boolean[SupS * SupS];
private static final boolean[] bestSolution = new boolean[SupS * SupS];

public String[] placeKnights(String[] board) {
init(board);
solve();
String[] solution = makeSolution();
Utils.debug("time", watch.getSecondString(), "score", score);
return solution;
}

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

Arrays.fill(attacksExpected, outside);
int sumAttacks = 0;
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
attacksExpected[z(r, c)] = (byte) (board[r].charAt(c) - '0');
sumAttacks += attacksExpected[z(r, c)];
}
}

Utils.debug("S", S, "sumAttacks", sumAttacks, "mean", (double) sumAttacks / (S * S));

for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
int z = z(r, c);
for (int d = 0; d < knightZ.length; d++) {
int kz = z + knightZ[d];

if (attacksExpected[kz] == outside) {
continue;
}

if (attacksActual[z] > attacksExpected[z]) {
deltaAdd[kz]++;
deltaRemove[kz]--;
} else if (attacksActual[z] < attacksExpected[z]) {
deltaAdd[kz]--;
deltaRemove[kz]++;
} else {
deltaAdd[kz]++;
deltaRemove[kz]++;
}
}
}
}

score = calculateScore();
bestScore = score;
}

private static final int z(int r, int c) {
return (r + 2) * SupS + (c + 2);
}

private void solve() {
SA();
}

private void SA() {

sa.startTime = watch.getSecond();

double second = 1;
int mask = (1 << 10) - 1;

sa.loop = 0;

A: for (;;) {

for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++, sa.loop++) {

if ((sa.loop & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {
saveBest();
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5d", score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastAcceptTemperature));
break A;
}

sa.updateTemperature();
if (sa.time > second) {
second++;
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5d", score), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastAcceptTemperature));
}

saveBest();
}

int z = z(r, c);

if (solution[z]) {
changeRemove(z);
} else {
changeAdd(z);
}
}
}

}
}

private void changeAdd(int z) {
assert !solution[z];

sa.countChange++;
if (deltaAdd[z] <= 0 || sa.accept(score + deltaAdd[z], score)) {
sa.countAccept++;
if (!(deltaAdd[z] <= 0)) {
sa.lastAcceptTemperature = sa.temperature;
}

solution[z] = true;
score += deltaAdd[z];

for (int d = 0; d < knightZ.length; d++) {
int kz = z + knightZ[d];
if (attacksExpected[kz] == outside) {
continue;
}

attacksActual[kz]++;

if (attacksActual[kz] - 1 == attacksExpected[kz]) {
for (int d2 = 0; d2 < knightZ.length; d2++) {
int kz2 = kz + knightZ[d2];
if (attacksExpected[kz2] == outside) {
continue;
}
deltaRemove[kz2] -= 2;
}
} else if (attacksActual[kz] == attacksExpected[kz]) {
for (int d2 = 0; d2 < knightZ.length; d2++) {
int kz2 = kz + knightZ[d2];
if (attacksExpected[kz2] == outside) {
continue;
}
deltaAdd[kz2] += 2;
}
}
}
}

}

private void changeRemove(int z) {
assert solution[z];

sa.countChange++;
if (deltaRemove[z] <= 0 || sa.accept(score + deltaRemove[z], score)) {
sa.countAccept++;
if (!(deltaRemove[z] <= 0)) {
sa.lastAcceptTemperature = sa.temperature;
}

score += deltaRemove[z];
solution[z] = false;

for (int d = 0; d < knightZ.length; d++) {
int kz = z + knightZ[d];
if (attacksExpected[kz] == outside) {
continue;
}

attacksActual[kz]--;

if (attacksActual[kz] + 1 == attacksExpected[kz]) {
for (int d2 = 0; d2 < knightZ.length; d2++) {
int kz2 = kz + knightZ[d2];
if (attacksExpected[kz2] == outside) {
continue;
}
deltaAdd[kz2] -= 2;
}
} else if (attacksActual[kz] == attacksExpected[kz]) {
for (int d2 = 0; d2 < knightZ.length; d2++) {
int kz2 = kz + knightZ[d2];
if (attacksExpected[kz2] == outside) {
continue;
}
deltaRemove[kz2] += 2;
}
}
}

}

}

private int calculateScore() {
int score = 0;
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
int z = z(r, c);
score += Math.abs(attacksActual[z] - attacksExpected[z]);
}
}
return score;
}

private void loadBest() {
score = bestScore;
System.arraycopy(bestSolution, 0, solution, 0, solution.length);
}

private void saveBest() {
if (score < bestScore) {
bestScore = score;
System.arraycopy(solution, 0, bestSolution, 0, solution.length);
}
}

private String[] makeSolution() {

String[] solution = new String[S];
for (int r = 0; r < S; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < S; c++) {
int z = z(r, c);
sb.append(this.solution[z] ? 'K' : '.');
}
solution[r] = sb.toString();
}
return solution;
}

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

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

KnightsAttacks ka = new KnightsAttacks();
String[] ret = ka.placeKnights(board);

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 SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1 * 9.5;
public double time = startTime;

public double startTemperature = 0.4;
public double endTemperature = 0.10;
public double temperature = startTemperature;
public double lastAcceptTemperature;

public int loop;
public int countChange;
public int countAccept;

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

public void updateTime() {
time = useTime ? KnightsAttacks.watch.getSecond() : loop;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double newScore, double currentScore) {
assert -(newScore - currentScore) < 0;
assert temperature >= 0;
return (-newScore + currentScore > -10 * (temperature) && (KnightsAttacks.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (-newScore + currentScore) / (temperature)));
}
}

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

}



このページのトップヘ