Score and Approach
- submission1
- ランダムプレイアウト
- ローカルの平均 : 0.965
- 何もしていないのにいいスコアが出た。と思っていたら130位くらいまで落ちた。
- submission2
- 多スタート + ランダムプレイアウト
- ローカルの平均 : 0.994
- 時間が余っていたので多スタートにする。
- submission3
- SA + ランダムプレイアウト
- ローカルの平均 : 0.9973
- 最初から全部やり直す必要はないなと思ったので、途中まで戻して、そこからランダムプレイアウトするSAにする。ここまでハイレベルのアプローチを強いものに変えていくことで順調に改善する。
- submission4
- 近傍を改善したSA + ランダムプレイアウト
- ローカルの平均 : 0.9978
- 途中まで戻していく時に、現在の解で消せてない場所を消せないか試して、1っ箇所消せたらそこからランダムプレイアウトするSAにする。全部消せる確率が上がった。
- submission5
- スコアがバラつくので同じ解を提出。順位も思ったより変わった。
- submission6
- 2つの近傍を使うSA + ランダムプレイアウト
- ローカルの平均 : 0.9989
- submission4の近傍と、途中まで戻して、現在の解で消せてない場所を消せないか試しながら、できるだけ現在の解を再現するようにする、という近傍を加える。
- このあたりでchokudai search を試すもスコアはSAの方が良かった。beam search は盤面をどう評価していいかわからなかったので、試せなかった。
- submission7
- パラメータチューニングした2つの近傍を使うSA + ランダムプレイアウト
- ローカルの平均 : 0.9992
- 多スタートにしたり、温度を変えて、パラメータチューニングした。
- submission8
- さらにパラメータチューニングした2つの近傍を使うSA + ランダムプレイアウト
- ローカルの平均 : 0.9993
- 多スタートをやめたり、温度を変えて、パラメータチューニングした。
source code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; public class SameColorPairs { private static final int[] dr = new int[] { -1, 0, 0, 1, }; private static final int[] dc = new int[] { 0, -1, 1, 0, }; private static final int EMPTY = -1; static final XorShift rng = new XorShift(System.nanoTime()); static final Watch watch = new Watch(); private int H; private int W; private int[][] board; private int numColors; private int best; private int[] bestHistory; private long hash; private long[][] hashes; private SAState sa = new SAState(); private HashSetusedHash = new HashSet<>(); private int[] currentHistory; private int bestTurn; private int numDeplications; private int[] solution; private int usedSize; private int[] bestSolution; private int[] solutionToIndex; private int numEmptys; private int numValids; public String[] removePairs(String[] board) { init(board); solve(); Utils.debug("numDeplications", numDeplications, "usedHash.size()", usedHash.size(), "numNexts", numNexts, "numEmptys", numEmptys, "numValids", numValids); return makeResult(); } private void init(String[] _board) { H = _board.length; W = _board[0].length(); board = new int[H][W]; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { board[r][c] = (_board[r].charAt(c) - '0'); } } numColors = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { numColors = Math.max(numColors, board[r][c] + 1); } } best = -1; history = new int[H * W / 2]; bestHistory = new int[H * W / 2]; used = new int[H][W]; queue = new int[H * W]; currentHistory = new int[H * W / 2]; hash = 0; hashes = new long[H][W]; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { hashes[r][c] = rng.nextLong(); } } usedSize = 0; solution = new int[H * W]; solutionToIndex = new int[H * W]; bestSolution = new int[H * W]; for (int i = 0; i < solution.length; i++) { solution[i] = i; bestSolution[i] = i; } for (int i = 0; i < solutionToIndex.length; i++) { solutionToIndex[solution[i]] = i; } for (int i = 0; i < solutionToIndex.length; i++) { assert solution[solutionToIndex[i]] == i; assert solutionToIndex[solution[i]] == i; } Utils.debug("H", H, "W", W, "H*W", H * W, "numColors", numColors); } private void solve() { SA(); Utils.debug("time", watch.getSecondString(), "score", best + "/" + (H * W), best * 1.0 / (H * W)); } private void saveBest() { if (numRemoved > best) { best = numRemoved; bestTurn = turn; System.arraycopy(history, 0, bestHistory, 0, turn); } } private void SA() { double second = Math.ceil(watch.getSecond()); sa.init(); for (;; sa.numIterations++) { { sa.updateTime(); if (best == (H * W) || sa.isTLE()) { Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%5d", numRemoved), String.format("%5d", best), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature)); break; } sa.updateTemperature(); sa.updateRange(); 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("%5d", numRemoved), String.format("%5d", best), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "numResultEmpty", numEmptys, "numResultValid", numValids); } } change(); } } private boolean first = true; private void change() { if (first || rng.nextDouble() < 0.5) { first = false; random(); } else { insert(); } } private void insert() { int randomTurn = (int) (turn * rng.nextDouble()); System.arraycopy(history, 0, currentHistory, 0, turn); int currentNumRemoved = numRemoved; int currentTurn = turn; ArrayList cantRemoved = new ArrayList<>(); for (int i = usedSize; i < solution.length; i++) { cantRemoved.add(solution[i]); } if (cantRemoved.size() == 0) { return; } for (; turn > randomTurn;) { previous(); } for (int t = turn; t < currentTurn;) { for (int i = 0; i < cantRemoved.size(); i++) { int v = cantRemoved.get(i).intValue(); int r = v / W; int c = v % W; if (board[r][c] == EMPTY) { continue; } int result = calculateMinDistanceSameColorPair(r, c); if (result == -1) { continue; } int r2 = (result >>> 16) & ((1 << 16) - 1); int c2 = (result >>> 0) & ((1 << 16) - 1); next(r, c, r2, c2); cantRemoved.remove(i); i--; } int v = currentHistory[t++]; int r = (v >>> 21) & 127; int c = (v >>> 14) & 127; int r2 = (v >>> 7) & 127; int c2 = (v >>> 0) & 127; if (board[r][c] != EMPTY && board[r2][c2] != EMPTY && canRemove(r, c, r2, c2)) { next(r, c, r2, c2); } else { continue; } } randomPlayout(); double deltaScore = numRemoved - currentNumRemoved; sa.validIterations++; if (deltaScore > -1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) { sa.acceptIterations++; if (!(deltaScore > -1e-9)) { sa.lastAcceptTemperature = sa.inverseTemperature; } saveBest(); } else { for (; turn > randomTurn;) { previous(); } for (; turn < currentTurn;) { int v = currentHistory[turn]; int r = (v >>> 21) & 127; int c = (v >>> 14) & 127; int r2 = (v >>> 7) & 127; int c2 = (v >>> 0) & 127; next(r, c, r2, c2); } } } private boolean canRemove(int r1, int c1, int r2, int c2) { assert board[r1][c1] != EMPTY; assert board[r1][c1] == board[r2][c2]; int minR = Math.min(r1, r2); int maxR = Math.max(r1, r2); int minC = Math.min(c1, c2); int maxC = Math.max(c1, c2); for (int r = minR; r <= maxR; r++) { for (int c = minC; c <= maxC; c++) { if (board[r][c] == EMPTY) { continue; } if (board[r][c] == board[r1][c1]) { continue; } return false; } } return true; } private void random() { int randomTurn = (int) (turn * rng.nextDouble()); System.arraycopy(history, randomTurn, currentHistory, randomTurn, turn - randomTurn); int currentNumRemoved = numRemoved; int currentTurn = turn; ArrayList cantRemoved = new ArrayList<>(); for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (board[r][c] == EMPTY) { continue; } cantRemoved.add((r << 16) | (c)); } } if (cantRemoved.size() == 0) { return; } turnLoop: for (; turn > randomTurn;) { previous(); for (int i = 0; i < 3; i++) { int v = cantRemoved.get((int) (cantRemoved.size() * rng.nextDouble())); int r = (v >>> 16) & ((1 << 16) - 1); int c = (v >>> 0) & ((1 << 16) - 1); int result = calculateMinDistanceSameColorPair(r, c); if (result != -1) { randomTurn = turn; int r2 = (result >>> 16) & ((1 << 16) - 1); int c2 = (result >>> 0) & ((1 << 16) - 1); long nextHash = hash ^ hashes[r][c] ^ hashes[r2][c2]; if (usedHash.add(nextHash)) { next(r, c, r2, c2); assert nextHash == hash; } else { numDeplications++; continue; } break turnLoop; } } } randomPlayout(); double deltaScore = numRemoved - currentNumRemoved; sa.validIterations++; if (deltaScore > -1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) { sa.acceptIterations++; if (!(deltaScore > -1e-9)) { sa.lastAcceptTemperature = sa.inverseTemperature; } saveBest(); } else { for (; turn > randomTurn;) { previous(); } for (; turn < currentTurn;) { int v = currentHistory[turn]; int r = (v >>> 21) & 127; int c = (v >>> 14) & 127; int r2 = (v >>> 7) & 127; int c2 = (v >>> 0) & 127; next(r, c, r2, c2); } } } private void randomPlayout() { for (;;) { shuffle(usedSize, solution.length, rng); boolean update = false; for (int i = usedSize; i < solution.length; i++) { int r = solution[i] / W; int c = solution[i] % W; if (board[r][c] == EMPTY) { continue; } int result = calculateMinDistanceSameColorPair(r, c); if (result == EMPTY) { numEmptys++; continue; } numValids++; int r2 = (result >>> 16) & ((1 << 16) - 1); int c2 = (result >>> 0) & ((1 << 16) - 1); long nextHash = hash ^ hashes[r][c] ^ hashes[r2][c2]; if (usedHash.add(nextHash)) { next(r, c, r2, c2); assert nextHash == hash; update = true; } else { numDeplications++; } } if (!update) { break; } } } private void shuffle(int startInclusive, int endExclusive, XorShift rng) { for (int i = endExclusive - 1; i >= startInclusive; i--) { int j = startInclusive + (int) ((i + 1 - startInclusive) * rng.nextDouble()); swap(i, j); } } private void swap(int i, int j) { int swap = solution[i]; solution[i] = solution[j]; solution[j] = swap; solutionToIndex[solution[i]] = i; solutionToIndex[solution[j]] = j; } private int numRemoved = 0; private int turn = 0; private int[] history; private int numNexts; private void next(int r, int c, int r2, int c2) { assert board[r][c] != EMPTY; assert board[r][c] == board[r2][c2]; numNexts++; history[turn++] = (board[r][c] << 28) | (r << 21) | (c << 14) | (r2 << 7) | (c2); board[r][c] = EMPTY; board[r2][c2] = EMPTY; numRemoved += 2; hash ^= hashes[r][c] ^ hashes[r2][c2]; swap(solutionToIndex[r * W + c], usedSize++); swap(solutionToIndex[r2 * W + c2], usedSize++); } private void previous() { int v = history[--turn]; int color = (v >>> 28) & 15; int r = (v >>> 21) & 127; int c = (v >>> 14) & 127; int r2 = (v >>> 7) & 127; int c2 = (v >>> 0) & 127; board[r][c] = color; board[r2][c2] = color; numRemoved -= 2; hash ^= hashes[r][c] ^ hashes[r2][c2]; usedSize -= 2; } private int[] queue; private int queueSize = 0; private int queueCurrent = 0; private int[][] used; private int numSearchs = 0; private int calculateMinDistanceSameColorPair(int r0, int c0) { numSearchs++; queueSize = 0; queueCurrent = 0; { queue[queueSize++] = ((r0 << 16) | (c0)); used[r0][c0] = numSearchs; } for (; queueCurrent < queueSize;) { int v = queue[queueCurrent++]; int r = (v >>> 16) & ((1 << 16) - 1); int c = (v >>> 0) & ((1 << 16) - 1); if (!(r == r0 && c == c0) && board[r][c] == board[r0][c0]) { return (r << 16) | (c); } for (int d = 0; d < dr.length; d++) { int nr = r + dr[d]; int nc = c + dc[d]; if (!isValid(nr, 0, H) || !isValid(nc, 0, W)) { continue; } if (used[nr][nc] == numSearchs) { continue; } if (board[nr][nc] != EMPTY && board[nr][nc] != board[r0][c0]) { continue; } if (nr > r0) { if (used[nr - 1][nc] == numSearchs) { } else { continue; } } else if (nr < r0) { if (used[nr + 1][nc] == numSearchs) { } else { continue; } } if (nc > c0) { if (used[nr][nc - 1] == numSearchs) { } else { continue; } } else if (nc < c0) { if (used[nr][nc + 1] == numSearchs) { } else { continue; } } used[nr][nc] = numSearchs; queue[queueSize++] = ((nr << 16) | (nc)); } } return EMPTY; } private boolean isValid(int v, int min, int minUpperBound) { return v >= min && v < minUpperBound; } private String[] makeResult() { ArrayList pairs = new ArrayList (); for (int t = 0; t < bestTurn; t++) { int v = bestHistory[t]; int r = (v >>> 21) & 127; int c = (v >>> 14) & 127; int r2 = (v >>> 7) & 127; int c2 = (v >>> 0) & 127; pairs.add("" + r + " " + c + " " + r2 + " " + c2); } return (String[]) pairs.toArray(new String[pairs.size()]); } public static void main(String[] args) { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int H = Integer.parseInt(br.readLine()); String[] board = new String[H]; for (int i = 0; i < H; ++i) { board[i] = br.readLine(); } SameColorPairs scp = new SameColorPairs(); String[] ret = scp.removePairs(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(); } } } 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 = 18; public double endTemperature = 4; public double inverseTemperature = 1.0 / startTemperature; public double lastAcceptTemperature = startTemperature; public double startRange = 1 << 20; public double endRange = 1 << 20; public double range = startRange; public int numIterations; public int validIterations; public int acceptIterations; public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; lastAcceptTemperature = startTemperature; startTime = useTime ? SameColorPairs.watch.getSecond() : numIterations; updateTime(); updateTemperature(); updateRange(); } public void updateTemperature() { inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0)); } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? SameColorPairs.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double newScore, double currentScore) { assert newScore - currentScore > 0; assert 1.0 / inverseTemperature >= 0; return SameColorPairs.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature)); } public boolean acceptUsingTomerunsPruning(double newScore, double currentScore) { assert newScore - currentScore > 0; assert 1.0 / inverseTemperature >= 0; return (-newScore + currentScore) * (inverseTemperature) > -10 && SameColorPairs.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature)); } public boolean acceptUsingTomerunsPruning(double deltaScore) { assert deltaScore < 0; assert 1.0 / inverseTemperature >= 0; return (deltaScore) * (inverseTemperature) > -10 && SameColorPairs.rng.nextDouble() < Math.exp((deltaScore) * (inverseTemperature)); } public boolean acceptUsingTomerunsPruningAndEvb(double newScore, double currentScore) { assert newScore - currentScore > 0; assert 1.0 / inverseTemperature >= 0; return (-newScore + currentScore) * (inverseTemperature) > -10 && (SameColorPairs.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (-newScore + currentScore) * (inverseTemperature)); } public boolean acceptUsingTomerunsPruningAndEvb(double deltaScore) { assert deltaScore < 0; assert 1.0 / inverseTemperature >= 0; return deltaScore * inverseTemperature > -10 && (SameColorPairs.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + deltaScore * inverseTemperature); } }