Approach 焼きなまし法を使いました。
- 初期解 : 入力された順に並べて、ランダムに回転する。
- 近傍 : ランダムに2点swap して、回転は４つ試して一番良いものを選ぶ。
- 3点swap を試したら悪くなった。
- 温度 : 線形に 0.25 -> 0.1
- 4辺が一致していないセルを保持する。そこから交換するセルを選ぶ。
- 1% ほど改善した。
- ランダムに2点swap -> 4辺が一致していないセルの隣のパネルを色が一致するパネルと swap する。
- 3% ほど改善した。
- 回転は片方だけでよいので、高速化もできた。
- 各セルのスコアを保持して高速化する。
- 0.5% ほど改善した。
- 4辺が一致していないセルの隣のパネルを色が一致するパネルと swap する。隣のパネルは色が一致していないものに限定する。
- N が小さいケースで悪くなったが、平均 1% ほど改善した。
- 4辺が一致していないセルの隣のパネルを色が一致するパネルと swap する。隣のパネルは色が一致していないものに限定する。（N <=10 のときは限定しない）
- 0.3% ほど改善した。（N <=10 のとき）
Source Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static final int[] dr = { -1, 0, 1, 0, };
private static final int[] dc = { 0, 1, 0, -1, };
private int N;
private int C;
final static XorShift rng = new XorShift(System.nanoTime());
final static Watch watch = new Watch();
private SAState sa = new SAState();
private double score;
private int[][] rxcToIndex;
private int[][] rxcToNumRotates;
private double bestScore;
private int[][] bestRxcToIndex;
private int[][] bestRxcToNumRotates;
private int[][] panelxDirectionToColor;
private IntSet notPerfectSet;
private int[] indexToRxc;
private ArrayList[] colorToPanels;
private int[][] rxcToScore;
public static void main(String[] args) {
new Main().run();
}
private void run() {
read();
solve();
write();
}
private void read() {
try (Scanner sc = new Scanner(System.in)) {
N = sc.nextInt();
C = sc.nextInt();
int PN = N * N;
panelxDirectionToColor = new int[PN][4];
for (int i = 0; i < PN; i++) {
int U = sc.nextInt();
int D = sc.nextInt();
int L = sc.nextInt();
int R = sc.nextInt();
panelxDirectionToColor[i][0] = U;
panelxDirectionToColor[i][1] = R;
panelxDirectionToColor[i][2] = D;
panelxDirectionToColor[i][3] = L;
}
rxcToIndex = new int[N][N];
rxcToNumRotates = new int[N][N];
bestRxcToIndex = new int[N][N];
bestRxcToNumRotates = new int[N][N];
notPerfectSet = new IntSet(N * N);
indexToRxc = new int[N * N];
colorToPanels = new ArrayList[C];
for (int color = 0; color < C; color++) {
colorToPanels[color] = new ArrayList<>();
}
for (int panel = 0; panel < N * N; panel++) {
for (int d = 0; d < 4; d++) {
int color = panelxDirectionToColor[panel][d];
colorToPanels[color].add(new NearPanel(panel, d, 0));
}
}
rxcToScore = new int[N][N];
} catch (Exception e) {
e.printStackTrace();
}
Utils.debug("N", N, "C", C);
}
public void solve() {
greedy();
SA();
}
private void greedy() {
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
rxcToIndex[r][c] = r * N + c;
rxcToNumRotates[r][c] = (int) (4 * rng.nextDouble());
indexToRxc[rxcToIndex[r][c]] = r * N + c;
}
}
score = calculateScore();
saveBest();
Utils.debug("greedy", "score", score, "time", watch.getSecondString());
}
private void SA() {
double second = (int) 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("%5.0f", score), String.format("%5.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
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("%5.0f", score), String.format("%5.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
}
}
mutate();
}
Utils.debug("SA", "score", score, "time", watch.getSecondString());
}
private void mutate() {
if (N <= 10) {
swap2();
} else {
swap2selectMismatch();
}
}
private void swap2() {
int v = notPerfectSet.get((int) (notPerfectSet.size() * rng.nextDouble()));
int r0 = v / N;
int c0 = v % N;
int direction0 = (int) (4 * rng.nextDouble());
int r = r0 + dr[direction0];
int c = c0 + dc[direction0];
if (r < 0 || r >= N || c < 0 || c >= N) {
return;
}
int panel0 = rxcToIndex[r0][c0];
int rotate0 = rxcToNumRotates[r0][c0];
int color0 = panelxDirectionToColor[panel0][(direction0 - rotate0 + 4) % 4];
ArrayList panels = colorToPanels[color0];
NearPanel p = panels.get((int) (panels.size() * rng.nextDouble()));
int v2 = indexToRxc[p.panel];
int r2 = v2 / N;
int c2 = v2 % N;
assert rxcToIndex[r2][c2] == p.panel;
if (r == r2 && c == c2) {
return;
}
if (r0 == r2 && c0 == c2) {
return;
}
int currentRotate = rxcToNumRotates[r][c];
int currentRotate2 = rxcToNumRotates[r2][c2];
int direction12 = getDirection(r, c, r2, c2);
int before = rxcToScore[r][c] + rxcToScore[r2][c2];
if (direction12 != -1) {
int panel = rxcToIndex[r][c];
int rotate = rxcToNumRotates[r][c];
int npanel = rxcToIndex[r2][c2];
int nrotate = rxcToNumRotates[r2][c2];
if (panelxDirectionToColor[panel][(direction12 - rotate + 4) % 4] == panelxDirectionToColor[npanel][((direction12 + 2) - nrotate + 4) % 4]) {
before--;
}
}
swap(r, c, r2, c2);
rxcToNumRotates[r][c] = ((direction0 + 2) - p.rotate + 4) % 4;
calculateBestRotate(r2, c2);
int scoreRC = calculateScore(r, c);
int scoreRC2 = calculateScore(r2, c2);
int after = scoreRC + scoreRC2;
if (direction12 != -1) {
int panel = rxcToIndex[r][c];
int rotate = rxcToNumRotates[r][c];
int npanel = rxcToIndex[r2][c2];
int nrotate = rxcToNumRotates[r2][c2];
if (panelxDirectionToColor[panel][(direction12 - rotate + 4) % 4] == panelxDirectionToColor[npanel][((direction12 + 2) - nrotate + 4) % 4]) {
after--;
}
}
int deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
update(r, c);
update(r2, c2);
updateScore(r, c, scoreRC);
updateScore(r2, c2, scoreRC2);
saveBest();
} else {
rxcToNumRotates[r][c] = currentRotate;
rxcToNumRotates[r2][c2] = currentRotate2;
swap(r, c, r2, c2);
}
}
private void swap2selectMismatch() {
int v = notPerfectSet.get((int) (notPerfectSet.size() * rng.nextDouble()));
int r0 = v / N;
int c0 = v % N;
int direction0 = (int) (4 * rng.nextDouble());
int r = r0 + dr[direction0];
int c = c0 + dc[direction0];
int direction02 = direction0;
if (r < 0 || r >= N || c < 0 || c >= N || isSameColor(r0, c0, direction0, r, c)) {
int direction1 = (int) (3 * rng.nextDouble());
if (direction1 >= direction0) {
direction1++;
}
r = r0 + dr[direction1];
c = c0 + dc[direction1];
direction02 = direction1;
if (r < 0 || r >= N || c < 0 || c >= N || isSameColor(r0, c0, direction1, r, c)) {
int direction2 = (int) (2 * rng.nextDouble());
if (direction2 >= direction0) {
direction2++;
}
if (direction2 >= direction1) {
direction2++;
}
r = r0 + dr[direction2];
c = c0 + dc[direction2];
direction02 = direction2;
if (r < 0 || r >= N || c < 0 || c >= N || isSameColor(r0, c0, direction2, r, c)) {
int direction3 = (int) (1 * rng.nextDouble());
if (direction3 >= direction0) {
direction3++;
}
if (direction3 >= direction1) {
direction3++;
}
if (direction3 >= direction2) {
direction3++;
}
r = r0 + dr[direction3];
c = c0 + dc[direction3];
direction02 = direction3;
if (r < 0 || r >= N || c < 0 || c >= N || isSameColor(r0, c0, direction3, r, c)) {
return;
}
}
}
}
direction0 = direction02;
int panel0 = rxcToIndex[r0][c0];
int rotate0 = rxcToNumRotates[r0][c0];
int color0 = panelxDirectionToColor[panel0][(direction0 - rotate0 + 4) % 4];
ArrayList panels = colorToPanels[color0];
NearPanel p = panels.get((int) (panels.size() * rng.nextDouble()));
int v2 = indexToRxc[p.panel];
int r2 = v2 / N;
int c2 = v2 % N;
assert rxcToIndex[r2][c2] == p.panel;
if (r == r2 && c == c2) {
return;
}
if (r0 == r2 && c0 == c2) {
return;
}
int currentRotate = rxcToNumRotates[r][c];
int currentRotate2 = rxcToNumRotates[r2][c2];
int direction12 = getDirection(r, c, r2, c2);
int before = rxcToScore[r][c] + rxcToScore[r2][c2];
if (direction12 != -1) {
int panel = rxcToIndex[r][c];
int rotate = rxcToNumRotates[r][c];
int npanel = rxcToIndex[r2][c2];
int nrotate = rxcToNumRotates[r2][c2];
if (panelxDirectionToColor[panel][(direction12 - rotate + 4) % 4] == panelxDirectionToColor[npanel][((direction12 + 2) - nrotate + 4) % 4]) {
before--;
}
}
swap(r, c, r2, c2);
rxcToNumRotates[r][c] = ((direction0 + 2) - p.rotate + 4) % 4;
calculateBestRotate(r2, c2);
int scoreRC = calculateScore(r, c);
int scoreRC2 = calculateScore(r2, c2);
int after = scoreRC + scoreRC2;
if (direction12 != -1) {
int panel = rxcToIndex[r][c];
int rotate = rxcToNumRotates[r][c];
int npanel = rxcToIndex[r2][c2];
int nrotate = rxcToNumRotates[r2][c2];
if (panelxDirectionToColor[panel][(direction12 - rotate + 4) % 4] == panelxDirectionToColor[npanel][((direction12 + 2) - nrotate + 4) % 4]) {
after--;
}
}
int deltaScore = after - before;
if (sa.accept(deltaScore)) {
score += deltaScore;
update(r, c);
update(r2, c2);
updateScore(r, c, scoreRC);
updateScore(r2, c2, scoreRC2);
saveBest();
} else {
rxcToNumRotates[r][c] = currentRotate;
rxcToNumRotates[r2][c2] = currentRotate2;
swap(r, c, r2, c2);
}
}
private boolean isSameColor(int r0, int c0, int direction0, int r, int c) {
return panelxDirectionToColor[rxcToIndex[r0][c0]][(direction0 - rxcToNumRotates[r0][c0] + 4) % 4] == panelxDirectionToColor[rxcToIndex[r][c]][((direction0 + 2) - rxcToNumRotates[r][c] + 4) % 4];
}
private void updateScore(int r, int c, int scoreRC) {
rxcToScore[r][c] = scoreRC;
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
continue;
}
rxcToScore[nr][nc] = calculateScore(nr, nc);
}
}
private void calculateBestRotate(int r, int c) {
int bestScore = (int) -1e9;
int bestRotate = -1;
for (int rotate = 0; rotate < 4; rotate++) {
rxcToNumRotates[r][c] = rotate;
int score = calculateScore(r, c);
if (score > bestScore) {
bestScore = score;
bestRotate = rotate;
}
}
rxcToNumRotates[r][c] = bestRotate;
}
private int getDirection(int r, int c, int r2, int c2) {
if (r == r2) {
if (c2 - c == 1) {
return 1;
} else if (c2 - c == -1) {
return 3;
}
} else if (c == c2) {
if (r2 - r == 1) {
return 2;
} else if (r2 - r == -1) {
return 0;
}
}
return -1;
}
private void update(int r, int c) {
if (calculateScore(r, c) < 4) {
notPerfectSet.add(r * N + c);
} else {
notPerfectSet.remove(r * N + c);
}
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
continue;
}
if (calculateScore(nr, nc) < 4) {
notPerfectSet.add(nr * N + nc);
} else {
notPerfectSet.remove(nr * N + nc);
}
}
}
private void swap(int r, int c, int r2, int c2) {
int swap = rxcToIndex[r][c];
rxcToIndex[r][c] = rxcToIndex[r2][c2];
rxcToIndex[r2][c2] = swap;
indexToRxc[rxcToIndex[r][c]] = r * N + c;
indexToRxc[rxcToIndex[r2][c2]] = r2 * N + c2;
}
private void write() {
final int x = 0;
final int y = 1;
final int rotate = 2;
int[][] ret = new int[N * N][3];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int index = rxcToIndex[r][c];
ret[index][x] = c;
ret[index][y] = r;
ret[index][rotate] = rxcToNumRotates[r][c];
}
}
for (int i = 0; i < N * N; ++i) {
System.out.println(ret[i][x] + " " + ret[i][y] + " " + ret[i][rotate]);
}
System.out.flush();
}
private int calculateScore() {
int score = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
int calculateScore = calculateScore(r, c);
rxcToScore[r][c] = calculateScore;
score += calculateScore;
if (calculateScore < 4) {
notPerfectSet.add(r * N + c);
}
}
}
return score / 2;
}
private int calculateScore(int r, int c) {
int score = 0;
for (int d = 0; d < dr.length; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
continue;
}
int panel = rxcToIndex[r][c];
int rotate = rxcToNumRotates[r][c];
int npanel = rxcToIndex[nr][nc];
int nrotate = rxcToNumRotates[nr][nc];
if (panelxDirectionToColor[panel][(d - rotate + 4) % 4] == panelxDirectionToColor[npanel][((d + 2) - nrotate + 4) % 4]) {
score++;
}
}
return score;
}
private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
bestRxcToIndex[r][c] = rxcToIndex[r][c];
bestRxcToNumRotates[r][c] = rxcToNumRotates[r][c];
}
}
}
}
private void loadBest() {
score = bestScore;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
rxcToIndex[r][c] = bestRxcToIndex[r][c];
rxcToNumRotates[r][c] = bestRxcToNumRotates[r][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 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 SAState {
public static final boolean useTime = true;
public double startTime = 0;
public double endTime = 9.5;
public double time = startTime;
public double startTemperature = 0.25;
public double endTemperature = 0.1;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;
public double startRange = 700;
public double endRange = 1;
public double range = startRange;
public int numIterations;
public int validIterations;
public int acceptIterations;
private static final double[] log = new double[32768];
static {
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
}
public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;
startTime = useTime ? Main.watch.getSecond() : numIterations;
update();
lastAcceptTemperature = inverseTemperature;
}
public void update() {
updateTime();
updateTemperature();
updateRange();
}
public void updateTemperature() {
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) {
return acceptB(deltaScore);
}
public boolean acceptB(double deltaScore) {
validIterations++;
if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}
assert deltaScore < 0 : Utils.toString(deltaScore);
assert 1.0 / inverseTemperature >= 0;
double d = deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Main.rng.nextInt() & 32767] < d) {
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;
double d = -deltaScore * inverseTemperature;
if (d < -10) {
return false;
}
if (log[Main.rng.nextInt() & 32767] < d) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}
}
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[value] = size;
size++;
return true;
}
public boolean remove(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
removeByIndex(index);
return true;
}
private boolean removeByIndex(int index) {
if (size == 0) {
return false;
}
assert index < size;
size--;
int value = indexToValue[index];
int value2 = indexToValue[size];
indexToValue[index] = value2;
valueToIndex[value2] = index;
indexToValue[size] = value;
valueToIndex[value] = EMPTY;
return true;
}
public void swap(int index, int index2) {
assert index < size;
assert index2 < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;
valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[index2]] = index2;
}
public void swapValue(int value, int value2) {
assert value < size;
assert value2 < size;
int swap = valueToIndex[value];
valueToIndex[value] = valueToIndex[value2];
valueToIndex[value2] = swap;
indexToValue[valueToIndex[value]] = value;
indexToValue[valueToIndex[value2]] = value2;
}
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;) {
removeByIndex(0);
}
}
public boolean contains(int value) {
return indexOf(value) != EMPTY;
}
@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(indexToValue, size()));
}
}
class NearPanel {
int panel;
int rotate;
int sameColors;
public NearPanel(int panel, int rotate, int sameColors) {
super();
this.panel = panel;
this.rotate = rotate;
this.sameColors = sameColors;
}
}
コメント