Approach simulated annealing を使いました。1億から4億イテレーション。
スコア
- knight の数 - 2 * 無効な knightの数
近傍
- ランダムな pawn でない点を選んで、フリップする。
- 攻撃されている数が2より多い点も含む。
- 含めたほうがいいかどうかは確認していない。
- 含めたほうがいいかどうかは確認していない。
- 攻撃されている数が2より多い点も含む。
- 無効な knight が有れば、
- この knight を取り除く。確率10%。
- この knight を攻撃している数が2より多いとき、攻撃している knight を1つ取り除く。2より少ないとき、攻撃している数が増えるように knight を置く。確率90%。
高速化
- 次の状態にするときのスコアの差を事前に計算しておく。
- 1次元の配列を使う。
SAの受理判定
- KnightsAttacks の wleite さんの受理判定を使ったら、ローカルでは5%くらいスコアが上がったけど、提出したら変わらなかった。(謎)
atsさんのマネ
- 無効な knight の保持は例の挿入、削除、ランダム取得がO(1)のsetを使った。
初期解
source code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class KnightsAndPawns { private static final int EMPTY = 0; private static final int PAWN = 1; private static final int KNIGHT = 2; private static final int[] dr = { -2, -2, -1, 1, 2, 2, 1, -1, }; private static final int[] dc = { -1, 1, 2, 2, 1, -1, -2, -2, }; private static final int[] dz = { -2, -2, -1, 1, 2, 2, 1, -1, }; private static final int[] dr2 = { 2, 0, -2, -1, -3, 3, 1, -4, 0, 4, -1, -3, 3, 1, -4, 0, -2, 2, 4, -3, -1, 1, 3, -4, 0, 4, -3, -1, 1, 3, -2, 0, 2, }; private static final int[] dc2 = { -4, -4, -4, -3, -3, -3, -3, -2, -2, -2, -1, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, }; static final XorShift rng = new XorShift(System.nanoTime()); static final Watch watch = new Watch(); private SAState sa = new SAState(); private int R; private int C; private int[] board; private int[] attacks; private int numKnights; private IntSet invalidSet; private double score; private boolean[] solution; private double bestScore; private boolean[] bestSolution; private int[] deltaScores; private IntSet[] directionSet; private int RC; public String[] placeKnights(String[] board) { init(board); solve(); return makeSolution(); } private void init(String[] board) { this.R = board.length; this.C = board[0].length(); RC = R * C; for (int i = 0; i < dz.length; i++) { dz[i] = z(dr[i], dc[i]); } this.board = new int[RC]; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { char charAt = board[r].charAt(c); if (charAt == '.') { this.board[z(r, c)] = EMPTY; } else if (charAt == 'P') { this.board[z(r, c)] = PAWN; } } } attacks = new int[RC]; for (int z = 0; z < RC; z++) { attacks[z] = calculateAttacks(z); } this.solution = new boolean[RC]; this.bestSolution = new boolean[RC]; score = 0; bestScore = 0; invalidSet = new IntSet(RC); directionSet = new IntSet[RC]; for (int z = 0; z < RC; z++) { directionSet[z] = new IntSet(8); } int numPawns = 0; for (int z = 0; z < RC; z++) { if (this.board[z] == PAWN) { numPawns++; } } Utils.debug("R", R, "C", C, "numPawns", numPawns, String.format("%.1f%%", numPawns * 100.0 / (R * C))); } private int calculateAttacks(int z) { int count = 0; for (int d = 0; d < dr.length; d++) { int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) { continue; } int z2 = z(r2, c2); if (board[z2] != EMPTY) { count++; } } return count; } 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; } private boolean isValid(int v, int min, int minUpper) { return v >= min && v < minUpper; } private void solve() { initDeltaScores(); SA(); } private void initDeltaScores() { if (deltaScores == null) { deltaScores = new int[RC]; } for (int z = 0; z < RC; z++) { if (board[z] == PAWN) { continue; } updateDeltaScore(z); } } 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("%7.2f", score), String.format("%7.2f", 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("%7.2f", score), String.format("%7.2f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature)); } } mutate(); } Utils.debug("SA", "time", watch.getSecondString()); } private void mutate() { if (invalidSet.size() > 0) { reduceInvalidKnight(); return; } flip(); } private void flip() { int z = (int) (RC * rng.nextDouble()); while (board[z] == PAWN) { z = (int) (RC * rng.nextDouble()); } if (sa.accept(deltaScores[z])) { score += deltaScores[z]; if (solution[z]) { removeKnight(z); } else { putKnight(z); } updateDeltaScores(z); saveBest(); assert score == calculateScore() : Utils.toString(sa.numIterations, sa.acceptIterations, score, calculateScore(), numKnights, invalidSet.size()); } } private boolean check() { assert invalidSet.size() == 0; for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { int z = z(r, c); assert calculateAttacks(z) == attacks[z]; if (solution[z]) { assert attacks[z] == 2; } } } return true; } private void reduceInvalidKnight() { int z = invalidSet.get((int) (invalidSet.size() * rng.nextDouble())); boolean removeMe = rng.nextDouble() < 0.1; if (removeMe) { if (sa.accept(deltaScores[z])) { score += deltaScores[z]; removeKnight(z); updateDeltaScores(z); saveBest(); } } else { if (attacks[z] > 2) { int d = (int) (dr.length * rng.nextDouble()); int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; int z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != KNIGHT) { return; } } } } if (sa.accept(deltaScores[z2])) { score += deltaScores[z2]; removeKnight(z2); updateDeltaScores(z2); saveBest(); } } else { int d = (int) (dr.length * rng.nextDouble()); int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; int z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) { d = (int) (dr.length * rng.nextDouble()); r2 = r(z) + dr[d]; c2 = c(z) + dc[d]; z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] != EMPTY) { return; } } } } if (sa.accept(deltaScores[z2])) { score += deltaScores[z2]; putKnight(z2); updateDeltaScores(z2); saveBest(); } } } } private void updateDeltaScores(int z) { for (int d = 0; d < dr.length; d++) { int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; int z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] == PAWN) { continue; } updateDeltaScore(z2); } for (int d = 0; d < dr2.length; d++) { int r2 = r(z) + dr2[d]; int c2 = c(z) + dc2[d]; int z2 = z(r2, c2); if (!isValid(r2, 0, R) || !isValid(c2, 0, C) || board[z2] == PAWN) { continue; } updateDeltaScore(z2); } } private void updateDeltaScore(int z) { if (solution[z]) { deltaScores[z] = (int) (calculateScoreRemove(z) - score); } else { deltaScores[z] = (int) (calculateScorePut(z) - score); } } private void putKnight(int z) { solution[z] = true; board[z] = KNIGHT; numKnights++; for (int d = 0; d < dr.length; d++) { int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) { continue; } int z2 = z(r2, c2); attacks[z2]++; if (solution[z2]) { if (attacks[z2] == 2) { invalidSet.removeValue(z2); } else { invalidSet.add(z2); } } directionSet[z2].add((d + 4) % dr.length); } if (attacks[z] == 2) { invalidSet.removeValue(z); } else { invalidSet.add(z); } } private void removeKnight(int z) { solution[z] = false; board[z] = EMPTY; numKnights--; for (int d = 0; d < dr.length; d++) { int r2 = r(z) + dr[d]; int c2 = c(z) + dc[d]; if (!isValid(r2, 0, R) || !isValid(c2, 0, C)) { continue; } int z2 = z(r2, c2); attacks[z2]--; if (solution[z2]) { if (attacks[z2] == 2) { invalidSet.removeValue(z2); } else { invalidSet.add(z2); } } directionSet[z2].removeValue((d + 4) % dr.length); } invalidSet.removeValue(z); } private double calculateScore() { return numKnights - 2 * invalidSet.size(); } private double calculateScorePut(int z) { int numInvalids = invalidSet.size(); for (int i = 0; i < directionSet[z].size(); i++) { int d = directionSet[z].get(i); int z2 = z + dz[d]; if (attacks[z2] == 1) { numInvalids--; } else if (attacks[z2] == 2) { numInvalids++; } } if (attacks[z] != 2) { numInvalids++; } return (numKnights + 1) - 2 * numInvalids; } private double calculateScoreRemove(int z) { int numInvalids = invalidSet.size(); for (int i = 0; i < directionSet[z].size(); i++) { int d = directionSet[z].get(i); int z2 = z + dz[d]; if (attacks[z2] == 3) { numInvalids--; } else if (attacks[z2] == 2) { numInvalids++; } } if (attacks[z] != 2) { numInvalids--; } return (numKnights - 1) - 2 * numInvalids; } private String[] makeSolution() { String[] res = new String[R]; for (int r = 0; r < R; r++) { StringBuilder line = new StringBuilder(); for (int c = 0; c < C; c++) { line.append(solution[z(r, c)] ? 'K' : '.'); } res[r] = line.toString(); } return res; } private void saveBest() { if (invalidSet.size() > 0) { return; } if (score > bestScore) { bestScore = score; for (int i = 0; i < RC; i++) { bestSolution[i] = solution[i]; } } } private void loadBest() { score = bestScore; for (int i = 0; i < RC; i++) { solution[i] = bestSolution[i]; } } 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(); } KnightsAndPawns kap = new KnightsAndPawns(); String[] ret = kap.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 = 9.5; public double time = startTime; public double startTemperature = 0.4; public double endTemperature = 0.1; public double inverseTemperature = 1.0 / startTemperature; public double lastAcceptTemperature = startTemperature; public double startRange = 0; public double endRange = 1e1; public double range = startRange; public int numIterations; public int validIterations; public int acceptIterations; private int lastAcceptIterations; final int[] log = new int[32768]; int remain; public void init() { numIterations = 0; validIterations = 0; acceptIterations = 0; startTime = useTime ? KnightsAndPawns.watch.getSecond() : numIterations; update(); lastAcceptTemperature = inverseTemperature; double start = KnightsAndPawns.watch.getSecond(); double m = -0.6 / (endTime - start) * (1 << 28); for (int i = 0; i < log.length; i++) { log[i] = (int) (m * Math.log((i + 0.5) / log.length)); } remain = (int) (endTime - start); } public void update() { updateTime(); updateTemperature(); updateRange(); } public void updateTemperature() { inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 0.5)); } public void updateRange() { range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0); } public void updateTime() { time = useTime ? KnightsAndPawns.watch.getSecond() : numIterations; remain = (int) (endTime - time); } public boolean isTLE() { return time >= endTime; } public boolean accept(int deltaScore) { return acceptB(deltaScore); } public boolean acceptB(int deltaScore) { validIterations++; if (deltaScore > -1e-9) { acceptIterations++; lastAcceptIterations = numIterations; return true; } if ((deltaScore > -6 && (-deltaScore << 28) <= log[KnightsAndPawns.rng.nextInt(log.length)] * remain)) { acceptIterations++; lastAcceptTemperature = inverseTemperature; lastAcceptIterations = numIterations; return true; } return false; } public boolean acceptS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } if (-deltaScore * inverseTemperature < -10) { return false; } if (KnightsAndPawns.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 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 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; } 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) { 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; } }