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());
	}

}