Approach 貪欲法 + 焼きなまし法(8.5秒) + 山登り法(1秒)を使いました。
貪欲法
- 行%2==1 かつ 列%2==1のマスに壁を作る。
- 近傍1:マンハッタン距離==2の2つのマスをflipする。(ただし、行%2==列%2のマスを除く)
- 1つのマスをflipする近傍を入れると悪くなった。
- 近傍2:空のマスに壁を作って、コの字型に回り道できるように壁を消す。(ただし、行%2==列%2のマスを除く)
- スコア計算:各色ごとに start と targets から幅優先探索してパス長を求めた。
- ビジュアライザより早いだけ。
- 壁の位置に関係する経路だけ再計算したら早くなりそうと思ったけどできなかった。(壁を消すときにどの経路が関係するかわからなくて実装できなかった。)
- 入口が1箇所だけのエリアだけ再計算したら早くなりそうと思ったけどできなかった。(時間がなかった。)
- 近傍1:1つのマスをflipする。
- 近傍2:斜めに隣接した2つのマスをflipする。
Example scores:
1) 110.0
2) 4295.0
3) 338.0
4) 780.0
5) 297.0
6) 1711.0
7) 310.0
8) 849.0
9) 1729.0
10) 2668.0
Source Code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; public class HardestMaze { private int N; private int numRobots; private int numTargets; private int T1; private Point[][] targets2; private boolean[][] isWall; private boolean[][] bestIsWall; private boolean[][] mustEmpty; private static final int[] dr = { 0, 1, 0, -1 }; private static final int[] dc = { -1, 0, 1, 0 }; private static final int[] dr8 = { -1, -2, -1, 0, 0, 1, 2, 1, }; private static final int[] dc8 = { -1, 0, 1, -2, 2, -1, 0, 1, }; private static final int INF = (int) 1e9; final static XorShift rng = new XorShift(System.nanoTime()); final static Watch watch = new Watch(); private SAState sa = new SAState(); private double score; private double bestScore; private InitializedIntArray map; private boolean[][][] isTarget; private int[][][] distance; private IntQueue queue; private int[][] best; public static void main(String[] args) { new HardestMaze().run(); } private void run() { read(); init(); solve(); write(); } private void read() { try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { N = Integer.parseInt(br.readLine()); numRobots = Integer.parseInt(br.readLine()); numTargets = Integer.parseInt(br.readLine()); T1 = numTargets + 1; Point[] starts; Point[][] targets; starts = new Point[numRobots]; targets = new Point[numRobots][numTargets]; targets2 = new Point[numRobots][T1]; for (int robot = 0; robot < numRobots; robot++) { String[] temp = br.readLine().split(" "); starts[robot] = new Point(Integer.parseInt(temp[0]), Integer.parseInt(temp[1])); for (int i = 0; i < numTargets; i++) { String[] temp2 = br.readLine().split(" "); targets[robot][i] = new Point(Integer.parseInt(temp2[0]), Integer.parseInt(temp2[1])); } for (int i = 0; i < numTargets; i++) { targets2[robot][i] = targets[robot][i]; } targets2[robot][numTargets] = starts[robot]; } } catch (Exception e) { e.printStackTrace(); } Utils.debug("N", N, "numRobots", numRobots, "numTargets", numTargets); } private void init() { isWall = new boolean[N][N]; bestIsWall = new boolean[N][N]; mustEmpty = new boolean[N][N]; for (int robot = 0; robot < numRobots; robot++) { for (Point point : targets2[robot]) { mustEmpty[point.r][point.c] = true; } } distance = new int[numRobots][T1][T1]; map = new InitializedIntArray((int) 1e9, N * N); isTarget = new boolean[numRobots][N][N]; for (int robot = 0; robot < numRobots; robot++) { for (int k = 0; k < numTargets; k++) { Point target = targets2[robot][k]; isTarget[robot][target.r][target.c] = true; } } best = new int[1 << T1][T1]; queue = new IntQueue(N * N); } private void solve() { greedy(); multiSA(); multiSA2(); } private void greedy() { for (int r = 1; r < N; r += 2) { for (int c = 1; c < N; c += 2) { if (mustEmpty[r][c]) { continue; } isWall[r][c] = true; } } score = calculateScore(); Utils.debug("greedy", "score", score, "time", watch.getSecondString()); } private void multiSA() { int numRestart = 1; double endTime = 8.5; double startTime = watch.getSecond(); double remainTime = endTime - startTime; double startStartTemperature = 4; double endStartTemperature = 0; sa.startRange = 1000; sa.endRange = 3; for (double restart = 0; restart < numRestart; restart++) { sa.startTime = startTime + remainTime * restart / numRestart; sa.endTime = startTime + remainTime * (restart + 1) / numRestart; sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart); SA(); } } private void multiSA2() { int numRestart = 1; double endTime = 9.5; double startTime = watch.getSecond(); double remainTime = endTime - startTime; double startStartTemperature = 0; double endStartTemperature = 0; sa.startRange = 1000; sa.endRange = 3; for (double restart = 0; restart < numRestart; restart++) { sa.startTime = startTime + remainTime * restart / numRestart; sa.endTime = startTime + remainTime * (restart + 1) / numRestart; sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart); SA2(); } } private void SA() { double second = Math.ceil(watch.getSecond()); sa.init(); for (;; ++sa.numIterations) { if ((sa.numIterations & ((1 << 3) - 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(); } } private void SA2() { double second = Math.ceil(watch.getSecond()); sa.init(); for (;; ++sa.numIterations) { if ((sa.numIterations & ((1 << 3) - 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()); } } mutate2(); } } private void mutate() { double random = 2 * rng.nextDouble(); if (random < 1) { flip2(); } else if (random < 2) { konoji(); } } private void mutate2() { double random = 2 * rng.nextDouble(); if (random < 1) { flipAll(); } else if (random < 2) { flip2All(); } } private void konoji() { int r = (int) (N * rng.nextDouble()); int c = (int) (N * rng.nextDouble()); if ((r & 1) == (c & 1)) { int d = (int) (dr.length * rng.nextDouble()); r += dr[d]; c += dc[d]; } if (!isValid(r) || !isValid(c)) { return; } if (isWall[r][c]) { return; } if (mustEmpty[r][c]) { return; } boolean[] current = new boolean[3]; boolean b = rng.nextDouble() < 0.5; if ((r & 1) == 1) { if (b) { if (isValid(c + 1)) { current[0] = isWall[r - 1][c + 1]; isWall[r - 1][c + 1] = false; } if (isValid(c + 2)) { current[1] = isWall[r + 0][c + 2]; isWall[r + 0][c + 2] = false; } if (isValid(r + 1) && isValid(c + 1)) { current[2] = isWall[r + 1][c + 1]; isWall[r + 1][c + 1] = false; } } else { if (isValid(c - 1)) { current[0] = isWall[r - 1][c - 1]; isWall[r - 1][c - 1] = false; } if (isValid(c - 2)) { current[1] = isWall[r + 0][c - 2]; isWall[r + 0][c - 2] = false; } if (isValid(r + 1) && isValid(c - 1)) { current[2] = isWall[r + 1][c - 1]; isWall[r + 1][c - 1] = false; } } } else { if (b) { if (isValid(r - 1)) { current[0] = isWall[r - 1][c - 1]; isWall[r - 1][c - 1] = false; } if (isValid(r - 2)) { current[1] = isWall[r - 2][c + 0]; isWall[r - 2][c + 0] = false; } if (isValid(r - 1) && isValid(c + 1)) { current[2] = isWall[r - 1][c + 1]; isWall[r - 1][c + 1] = false; } } else { if (isValid(r + 1)) { current[0] = isWall[r + 1][c - 1]; isWall[r + 1][c - 1] = false; } if (isValid(r + 2)) { current[1] = isWall[r + 2][c + 0]; isWall[r + 2][c + 0] = false; } if (isValid(r + 1) && isValid(c + 1)) { current[2] = isWall[r + 1][c + 1]; isWall[r + 1][c + 1] = false; } } } isWall[r][c] = true; double deltaScore = calculateScore() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); } else { if ((r & 1) == 1) { if (b) { if (isValid(c + 1)) { isWall[r - 1][c + 1] = current[0]; } if (isValid(c + 2)) { isWall[r + 0][c + 2] = current[1]; } if (isValid(r + 1) && isValid(c + 1)) { isWall[r + 1][c + 1] = current[2]; } } else { if (isValid(c - 1)) { isWall[r - 1][c - 1] = current[0]; } if (isValid(c - 2)) { isWall[r + 0][c - 2] = current[1]; } if (isValid(r + 1) && isValid(c - 1)) { isWall[r + 1][c - 1] = current[2]; } } } else { if (b) { if (isValid(r - 1)) { isWall[r - 1][c - 1] = current[0]; } if (isValid(r - 2)) { isWall[r - 2][c + 0] = current[1]; } if (isValid(r - 1) && isValid(c + 1)) { isWall[r - 1][c + 1] = current[2]; } } else { if (isValid(r + 1)) { isWall[r + 1][c - 1] = current[0]; } if (isValid(r + 2)) { isWall[r + 2][c + 0] = current[1]; } if (isValid(r + 1) && isValid(c + 1)) { isWall[r + 1][c + 1] = current[2]; } } } isWall[r][c] = false; } } public static final void shuffle(boolean[] a, XorShift rng) { for (int i = a.length - 1; i >= 0; i--) { int j = (int) ((i + 1) * rng.nextDouble()); swap(a, i, j); } } public static final void swap(boolean[] a, int i, int j) { boolean swap = a[i]; a[i] = a[j]; a[j] = swap; } private void flip2() { int r = (int) (N * rng.nextDouble()); int c = (int) (N * rng.nextDouble()); if ((r & 1) == (c & 1)) { int d = (int) (dr.length * rng.nextDouble()); r += dr[d]; c += dc[d]; } if (!isValid(r) || !isValid(c)) { return; } int d = (int) (dr8.length * rng.nextDouble()); int r2 = r + dr8[d]; int c2 = c + dc8[d]; if (!isValid(r2) || !isValid(c2)) { return; } if (!isWall[r][c]) { if (mustEmpty[r][c]) { return; } } if (!isWall[r2][c2]) { if (mustEmpty[r2][c2]) { return; } } isWall[r][c] = !isWall[r][c]; isWall[r2][c2] = !isWall[r2][c2]; double deltaScore = calculateScore() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); } else { isWall[r][c] = !isWall[r][c]; isWall[r2][c2] = !isWall[r2][c2]; } } private void flip2All() { int r = (int) (N * rng.nextDouble()); int c = (int) (N * rng.nextDouble()); int d = (int) (dr8.length * rng.nextDouble()); int r2 = r + dr8[d]; int c2 = c + dc8[d]; if (!isValid(r2) || !isValid(c2)) { return; } if (!isWall[r][c]) { if (mustEmpty[r][c]) { return; } } if (!isWall[r2][c2]) { if (mustEmpty[r2][c2]) { return; } } isWall[r][c] = !isWall[r][c]; isWall[r2][c2] = !isWall[r2][c2]; double deltaScore = calculateScore() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); } else { isWall[r][c] = !isWall[r][c]; isWall[r2][c2] = !isWall[r2][c2]; } } private void flipAll() { int r = (int) (N * rng.nextDouble()); int c = (int) (N * rng.nextDouble()); if (!isWall[r][c]) { if (mustEmpty[r][c]) { return; } } isWall[r][c] = !isWall[r][c]; double deltaScore = calculateScore() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); } else { isWall[r][c] = !isWall[r][c]; } } private void saveBest() { if (score > bestScore) { bestScore = score; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { bestIsWall[r][c] = isWall[r][c]; } } } } private void loadBest() { score = bestScore; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { isWall[r][c] = bestIsWall[r][c]; } } } private double calculateScore() { allPairsShortestPath2(); double score = 0; final int S2 = 1 << T1; for (int robot = 0; robot < numRobots; robot++) { for (int S = 0; S < S2; S++) { for (int i = 0; i < T1; i++) { best[S][i] = INF; } } int start = numTargets; best[1 << start][start] = 0; for (int S = 0; S < S2; S++) { if ((S & (1 << start)) == 0) { continue; } for (int i = 0; i < T1; i++) { if ((S & (1 << i)) == 0) { continue; } for (int j = 0; j < numTargets; j++) { if ((S & (1 << j)) != 0) { continue; } if (best[S | (1 << j)][j] > best[S][i] + distance[robot][i][j]) { best[S | (1 << j)][j] = best[S][i] + distance[robot][i][j]; } } } } int bestEnd = -1; { double min = INF; for (int end = 0; end < numTargets; end++) { if (best[S2 - 1][end] < min) { min = best[S2 - 1][end]; bestEnd = end; } } } if (bestEnd == -1) { return -INF; } score += best[S2 - 1][bestEnd]; } return score; } private void allPairsShortestPath2() { for (int robot = 0; robot < numRobots; robot++) { for (int from = 0; from < T1; from++) { Point pointFrom = targets2[robot][from]; bfs(robot, pointFrom.r, pointFrom.c); for (int to = 0; to < T1; to++) { Point pointTo = targets2[robot][to]; distance[robot][from][to] = map.get(mapIndex(pointTo)); } } } } private int mapIndex(Point pointTo) { return pointTo.r * N + pointTo.c; } private void bfs(int robot, int r2, int c2) { queue.clear(); map.clear(); { map.set(r2 * N + c2, 0); queue.add((r2 << 6) | c2); } int countTarget = 0; for (; !queue.isEmpty();) { int v = queue.poll(); int distance = (v >>> 12); int r = (v >>> 6) & 63; int c = (v >>> 0) & 63; if (isTarget[robot][r][c]) { countTarget++; if (countTarget >= numTargets) { break; } } 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 (isWall[nr][nc]) { continue; } if (map.get(nr * N + nc) < INF) { continue; } map.set(nr * N + nc, distance + 1); queue.add(((distance + 1) << 12) | (nr << 6) | nc); } } } private boolean isValid(int v) { return v >= 0 && v < N; } public static finalArrayList reverse(ArrayList list) { for (int l = 0, r = list.size() - 1; l < r; l++, r--) { list.set(r, list.set(l, list.get(r))); } return list; } private void write() { System.out.println(N * N); for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { System.out.println(isWall[r][c] ? '#' : '.'); } } System.out.flush(); } } class Point { int r; int c; public Point(int r, int c) { super(); this.r = r; this.c = c; } } class SAState { public static final boolean useTime = true; public double startTime = 0; public double endTime = 9.5; public double time = startTime; public double startTemperature = 30; public double endTemperature = 1e-9; public double inverseTemperature = 1.0 / startTemperature; public double lastAcceptTemperature = startTemperature; public double startRange = 1000; public double endRange = 3; 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 ? HardestMaze.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 ? HardestMaze.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double deltaScore) { return acceptB(deltaScore); } public boolean acceptHC(double deltaScore) { return acceptHCS(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[HardestMaze.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[HardestMaze.rng.nextInt() & 32767] < d) { acceptIterations++; lastAcceptTemperature = inverseTemperature; return true; } return false; } public boolean acceptHCS(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } return false; } } class InitializedIntArray { private int[] values; private int[] initial_values; private int[] epoch; private int current_epoch; public InitializedIntArray(int[] initial_values) { init(initial_values); } public InitializedIntArray(int initial_value, int size) { init(initial_value, size); } public void init(int[] initial_values) { current_epoch = 0; this.initial_values = Arrays.copyOf(initial_values, initial_values.length); values = Arrays.copyOf(initial_values, initial_values.length); epoch = new int[values.length]; } public void init(int initial_value, int size) { current_epoch = 0; initial_values = new int[size]; Arrays.fill(initial_values, initial_value); this.values = Arrays.copyOf(initial_values, initial_values.length); epoch = new int[values.length]; } public void clear() { current_epoch++; } public int get(int at) { assert (at < values.length); if (epoch[at] != current_epoch) { epoch[at] = current_epoch; values[at] = initial_values[at]; } return values[at]; } public void set(int at, int value) { assert (at < values.length); epoch[at] = current_epoch; values[at] = value; } } class IntQueue { private static final int EMPTY = -1; private int[] values; private int current; private int size; public IntQueue(int capacity) { values = new int[capacity]; clear(); } public void clear() { current = 0; size = 0; } public int size() { return size - current; } public boolean isEmpty() { return size() <= 0; } public boolean contains(int value) { return indexOf(value) != EMPTY; } public int indexOf(int value) { for (int i = current; i < size; i++) { if (values[i] == value) { return i; } } return EMPTY; } public int poll() { return values[current++]; } public boolean add(int value) { values[size++] = value; return true; } public boolean remove(int value) { int index = indexOf(value); if (index == EMPTY) { return false; } for (int i = index; i < size; i++) { values[i] = values[i + 1]; } size--; return true; } } 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()); } } 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); } }
コメント