Score and Rank 812700.54 暫定31位
Approach
- submission1
- Approach : exampleの初期解 + SA
- 近傍1 : ランダムにregionを選んで、ランダムな色に変える。
- 近傍2 : ランダムにregionを選んで、隣の隣のregionの色を同じにする。
- 使った色数が収束しなかった。
- submission2
- score : 25%改善
- Approach : 初期解 beam search + SA
- 近傍1 : ランダムにregionを選んで、ランダムな色に変える。
- 近傍2 : ランダムにregionを選んで、隣の隣のregionの色を同じにする。
- 近傍3 : ランダムにregionを選んで、隣のregionと色を交換する。
- 使った色数が減った分改善した。
- submission3
- score : 16%改善
- Approach : 初期解 beam search + SA
- 近傍1 : ランダムにregionを選んで、現在使っている色から1つ除いた中でランダムな色に変える。
- 使った色数が7になりやすくなった。
- submission4
- score : 11%改善
- Approach : 初期解 beam search + 使った色数を減らす用のSA + scoreを減らす用のSA
- 使った色数を減らす用のSAの近傍 : ランダムにregionを選んで、現在使っている色から1つ除いた中でランダムな色に変える。
- scoreを減らす用のSAの近傍 : ランダムにregionを選んで、現在使っている色の中からランダムな色に変える。
- 使った色数が収束したあと、スコアが改善しやすくなった。それでも、半分近くのregionで今の色以外は使えないという状態だった。
- 問題を4色問題(4色定理)に変更してみても、小さいケース以外は5色にしかならなかった。
- submission5
- score : 1%改善
- Approach : 初期解 greedy + 使った色数を減らす用のSA + scoreを減らす用のSA
- 高速化した。
- 初期解を作るのにbeam searchを使う意味がないのでgreedyに変更。
- submission6
- score : 0.3%改善
- Approach : 初期解 greedy + 使った色数を減らす用のSA + scoreを減らす用のSA
- scoreを減らす用のSAを多スタート(4回)した。
source code
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; public class MapRecoloring { static final XorShift rng = new XorShift(System.nanoTime()); static final Watch watch = new Watch(); private static final int EMPTY = -1; private int H; private int W; private int numRegions; private int numColors; private double score; private int[] regionToColor; private double bestScore; private int[] bestRegionToColor; private int[][] regionToContiguousRegions; private HashSet[] colorToRegions; private int[] regionToValidColorsSize; private int[][] regionToValidColors; private int[][] regionToColorToIndex; private SAState sa = new SAState(); private int[][] regionAndColorToNumColors; private int[] regionToArea; private int usedColors; private int numRepaints; public int[] recolor(int H, int[] regions, int[] oldColors) { Utils.debug("recolor", "time", watch.getSecondString()); init(H, regions, oldColors); solve(); return makeSolution(); } private void init(int H, int[] regions, int[] oldColors) { Utils.debug("init", "time", watch.getSecondString()); this.H = H; this.W = oldColors.length / H; numRegions = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { numRegions = Math.max(numRegions, 1 + regions[r * W + c]); } } numColors = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { numColors = Math.max(numColors, 1 + oldColors[r * W + c]); } } regionToArea = new int[numRegions]; regionAndColorToNumColors = new int[numRegions][numRegions]; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { int region = regions[r * W + c]; int color = oldColors[r * W + c]; regionAndColorToNumColors[region][color]++; regionToArea[region]++; } } regionToContiguousRegions = new int[numRegions][]; HashSet [] regionToRegions = new HashSet[numRegions]; for (int region = 0; region < numRegions; region++) { regionToRegions[region] = new HashSet<>(); } for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { int region = regions[r * W + c]; if (c + 1 < W) { int regionC = regions[r * W + c + 1]; if (region != regionC) { regionToRegions[region].add(regionC); regionToRegions[regionC].add(region); } } if (r + 1 < H) { int regionR = regions[(r + 1) * W + c]; if (region != regionR) { regionToRegions[region].add(regionR); regionToRegions[regionR].add(region); } } } } for (int region = 0; region < numRegions; region++) { HashSet contiguousRegions = regionToRegions[region]; regionToContiguousRegions[region] = new int[contiguousRegions.size()]; int i = 0; for (Integer contiguousRegion : contiguousRegions) { regionToContiguousRegions[region][i++] = contiguousRegion.intValue(); } } regionToColor = new int[numRegions]; Arrays.fill(regionToColor, EMPTY); colorToRegions = new HashSet[numRegions]; for (int i = 0; i < colorToRegions.length; i++) { colorToRegions[i] = new HashSet<>(); } bestRegionToColor = new int[numRegions]; regionToValidColorsSize = new int[numRegions]; regionToValidColors = new int[numRegions][32]; regionToColorToIndex = new int[numRegions][32]; int minRepaints = 0; for (int region = 0; region < numRegions; region++) { int numRepaints = (int) 1e9; for (int color = 0; color < numColors; color++) { numRepaints = Math.min(numRepaints, regionToArea[region] - regionAndColorToNumColors[region][color]); } minRepaints += numRepaints; } Utils.debug("minRepaints", minRepaints, "H*W", H * W); Utils.debug("H", H, "W", W, "numRegions", numRegions, "numColors", numColors, "time", watch.getSecondString()); } private void solve() { greedy(); initValidColors(); sa.startTime = watch.getSecond(); sa.endTime = sa.startTime + 1; usedColorsSA(); score = calculateScore(); bestScore = 1e9; saveBest(); int numRestart = 4; double startTemperature = 100; double endTemperature = 100; double startTime = watch.getSecond(); double endTime = 9.5; for (int restart = 0; restart < numRestart; restart++) { initValidColors(); sa.startTemperature = startTemperature + restart * (endTemperature - startTemperature) / numRestart; sa.endTemperature = 0; sa.startTime = startTime + restart * (endTime - startTime) / numRestart; sa.endTime = startTime + (restart + 1) * (endTime - startTime) / numRestart; scoreSA(); loadBest(); } } private void greedy() { for (int region = 0; region < numRegions; region++) { for (int color = 0; color < numRegions; color++) { if (canUse(region, color)) { set(region, color); break; } } } score = calculateScore(); bestScore = 1e9; saveBest(); Utils.debug("greedy", "score", score, "usedColors", calculateUsedColors(), "numRepaints", calculateScore() / calculateUsedColors(), "time", watch.getSecondString()); } private void usedColorsSA() { double second = Math.ceil(watch.getSecond()); score = calculateUsedColors(); sa.init(); for (int i = 0;; sa.numIterations++) { if ((++i & ((1 << 10) - 1)) == 0) { sa.update(); if (sa.isTLE()) { Utils.debug(sa.numIterations, sa.validIterations, 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)); break; } if (watch.getSecond() > second) { second++; Utils.debug(sa.numIterations, sa.validIterations, 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)); } } int region = (int) (numRegions * rng.nextDouble()); for (int j = 0; j < regionToValidColorsSize[region]; j++) { int color = regionToValidColors[region][j]; if (color == regionToColor[region]) { continue; } if (color >= usedColors - 1) { remove(region, regionToColorToIndex[region][color]); continue; } int currentColor = regionToColor[region]; clear(region); set(region, color); double deltaScore = (double) calculateUsedColors() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); updateValidColors(region, color, currentColor); break; } else { clear(region); set(region, currentColor); } } } } private void scoreSA() { double second = Math.ceil(watch.getSecond()); sa.init(); for (int i = 0;; sa.numIterations++) { if ((++i & ((1 << 10) - 1)) == 0) { sa.update(); if (sa.isTLE()) { Utils.debug(sa.numIterations, sa.validIterations, 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)); break; } } if ((i & ((1 << 15) - 1)) == 0) { swapRegionColor(); } else { int region = (int) (numRegions * rng.nextDouble()); while (regionToValidColorsSize[region] == 0) { region = (int) (numRegions * rng.nextDouble()); } int color = regionToValidColors[region][(int) (regionToValidColorsSize[region] * rng.nextDouble())]; if (color >= usedColors) { remove(region, regionToColorToIndex[region][color]); continue; } int currentColor = regionToColor[region]; clear(region); set(region, color); double deltaScore = calculateScore() - score; if (sa.accept(deltaScore)) { score += deltaScore; saveBest(); updateValidColors(region, color, currentColor); } else { clear(region); set(region, currentColor); } } } } private void swapRegionColor() { int color = (int) (usedColors * rng.nextDouble()); int color2 = (int) (numColors * rng.nextDouble()); while (color2 == color) { color2 = (int) (numColors * rng.nextDouble()); } double deltaScore = 0; for (Integer region : colorToRegions[color]) { deltaScore -= regionToArea[region] - regionAndColorToNumColors[region][color]; deltaScore += regionToArea[region] - regionAndColorToNumColors[region][color2]; } for (Integer region : colorToRegions[color2]) { deltaScore -= regionToArea[region] - regionAndColorToNumColors[region][color2]; deltaScore += regionToArea[region] - regionAndColorToNumColors[region][color]; } if (sa.accept(deltaScore)) { HashSet copy = new HashSet (); copy.addAll(colorToRegions[color]); HashSet copy2 = new HashSet (); copy2.addAll(colorToRegions[color2]); for (Integer region : copy) { clear(region.intValue()); set(region.intValue(), color2); } for (Integer region : copy2) { clear(region.intValue()); set(region.intValue(), color); } score += deltaScore; saveBest(); initValidColors(); } else { } } private void initValidColors() { for (int region = 0; region < numRegions; region++) { Arrays.fill(regionToColorToIndex[region], EMPTY); regionToValidColorsSize[region] = 0; for (int color = 0; color < usedColors; color++) { if (color == regionToColor[region]) { continue; } if (!canUse(region, color)) { continue; } add(region, color); } } } private void updateValidColors(int region, int color, int oldColor) { for (int contiguousRegion : regionToContiguousRegions[region]) { int indexOf = regionToColorToIndex[contiguousRegion][color]; if (indexOf != EMPTY) { remove(contiguousRegion, indexOf); } if (canUse(contiguousRegion, oldColor)) { add(contiguousRegion, oldColor); } } { int indexOf = regionToColorToIndex[region][color]; remove(region, indexOf); add(region, oldColor); } } private void add(int region, int color) { int index = regionToValidColorsSize[region]; regionToValidColors[region][index] = color; regionToColorToIndex[region][color] = index; regionToValidColorsSize[region]++; } private void remove(int region, int index) { int lastIndex = regionToValidColorsSize[region] - 1; int swap = regionToValidColors[region][index]; regionToValidColors[region][index] = regionToValidColors[region][lastIndex]; regionToValidColors[region][lastIndex] = swap; regionToColorToIndex[region][regionToValidColors[region][index]] = index; regionToColorToIndex[region][regionToValidColors[region][lastIndex]] = EMPTY; regionToValidColorsSize[region]--; } private boolean canUse(int region, int color) { for (int contiguousRegion : regionToContiguousRegions[region]) { if (color == regionToColor[contiguousRegion]) { return false; } } return true; } private int calculateScore() { return usedColors * numRepaints; } private int calculateUsedColors() { return usedColors; } private void set(int region, int color) { assert regionToColor[region] == EMPTY; regionToColor[region] = color; if (colorToRegions[color].size() == 0) { usedColors++; } colorToRegions[color].add(region); numRepaints += regionToArea[region] - regionAndColorToNumColors[region][color]; } private void clear(int region) { int color = regionToColor[region]; regionToColor[region] = EMPTY; if (colorToRegions[color].size() == 1) { usedColors--; } colorToRegions[color].remove(region); numRepaints -= regionToArea[region] - regionAndColorToNumColors[region][color]; } private void saveBest() { if (score < bestScore) { bestScore = score; for (int region = 0; region < numRegions; region++) { bestRegionToColor[region] = regionToColor[region]; } } } private void loadBest() { score = bestScore; for (int region = 0; region < numRegions; region++) { clear(region); set(region, bestRegionToColor[region]); } } private int[] makeSolution() { return regionToColor; } public static void main(String[] args) { Utils.debug("main", "time", watch.getSecondString()); try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) { int H = Integer.parseInt(br.readLine()); int S = Integer.parseInt(br.readLine()); int[] regions = new int[S]; for (int i = 0; i < S; ++i) { regions[i] = Integer.parseInt(br.readLine()); } int R = Integer.parseInt(br.readLine()); int[] oldColors = new int[R]; for (int i = 0; i < R; ++i) { oldColors[i] = Integer.parseInt(br.readLine()); } MapRecoloring mr = new MapRecoloring(); int[] ret = mr.recolor(H, regions, oldColors); 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 = 1e2; public double endTemperature = 0; 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; startTime = useTime ? MapRecoloring.watch.getSecond() : numIterations; update(); lastAcceptTemperature = inverseTemperature; } public void update() { 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 ? MapRecoloring.watch.getSecond() : numIterations; } public boolean isTLE() { return time >= endTime; } public boolean accept(double deltaScore) { validIterations++; if (deltaScore < 1e-9) { acceptIterations++; return true; } assert deltaScore > 0; assert 1.0 / inverseTemperature >= 0; if (MapRecoloring.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()); } }
コメント