EvbCFfp1XB

problem and my answer.



Approach SA(1 case あたり 約1550点)

近傍
  • 1つずらす(縦長だったら上、下両方試していい方へ移動) (遷移確率5%)
  • ランダムに形と位置を変える(遷移確率47.5%)
  • 2つのstickを入れ替える(遷移確率47.5%)

Greedy (約1230点)

  • L[k]の長いkから決める
  • 全探索して最もスコアが良くなる位置、形を選ぶ

Greedy (約1330点)

  • L[k]の長いkから決める
  • 全探索して最もスコアが良くなる位置、形を選ぶ
  • stickの端点と外の点が違う色になる時に減点する

感想

  • SAって1秒でもうまくいくんだなーと思った。
  • assert 文も実行される仕様になかなか気づかなかった。

追記
Approach
SA(約1600)
  • 1つずらす(縦長だったら上、下両方試していい方へ移動ではなく、片方決めうちのほうが精度が良かった)(確率0%(精度は良くなったけど必要なかった))
  • ランダムに形と位置を変える(確率15%)
  • 長さが1違う2つのstickを入れ替える(確率85%)
  • https://yukicoder.me/submissions/262524


source code



import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

String line = br.readLine();
String[] split = line.split(" ");
int N = Integer.parseInt(split[0]);
int K = Integer.parseInt(split[1]);

line = br.readLine();
split = line.split(" ");
int[] L = new int[K];
for (int i = 0; i < K; i++) {
L[i] = Integer.parseInt(split[i]);
}

int[][] A = new int[N][N];
for (int r = 0; r < N; r++) {
line = br.readLine();
for (int c = 0; c < N; c++) {
A[r][c] = line.charAt(c) - '0';
}
}

String ret = new Main().run(N, K, L, A);
System.out.println(ret);
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

private double score;
private double bestScore;
static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());
private SAState sa = new SAState();
private int N;
private int K;
private int[] L;
private int[][] A;
private int W0;
private boolean[] isVerticals;
private int[] rs;
private int[] cs;
private boolean[] bestIsVerticals;
private int[] bestRs;
private int[] bestCs;

private String run(int N, int K, int[] L, int[][] A) {
init(N, K, L, A);
greedy();
SA();
return makeSolution();
}

private void init(int n, int k, int[] l, int[][] a) {

N = n;
K = k;
L = l;
A = a;

isVerticals = new boolean[K];
rs = new int[K];
cs = new int[K];

bestIsVerticals = new boolean[K];
bestRs = new int[K];
bestCs = new int[K];

W0 = 0;
W0 = calculateScore(a);

Utils.debug("init", "time", watch.getSecondString());
}

private void greedy() {
for (int k = 0; k < K; k++) {
isVerticals[k] = rng.nextDouble() < 0.5;
if (isVerticals[k]) {
rs[k] = (int) ((N - L[k]) * rng.nextDouble());
cs[k] = (int) (N * rng.nextDouble());
} else {
rs[k] = (int) (N * rng.nextDouble());
cs[k] = (int) ((N - L[k]) * rng.nextDouble());
}

flip(k, isVerticals[k], rs[k], cs[k]);
}
}

private void SA() {
score = calculateScore(A);
bestScore = -1e99;
saveBest();

sa.startTime = watch.getSecond();
sa.endTime = 0.85;
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;
}
}

mutate();
}
Utils.debug("SA", "time", watch.getSecondString());
}

private void mutate() {
int random = (int) (100 * rng.nextDouble());
if (random < 5) {
move();
} else if (random < 52) {
random();
} else {
swap();
}
}

private void random() {
int k = (int) (K * rng.nextDouble());

boolean currentIsVertical = isVerticals[k];
int currentR = rs[k];
int currentC = cs[k];

boolean newIsVertical = rng.nextDouble() < 0.5;
int newR = currentR + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble());
int newC = currentC + (int) (-sa.range * 0.5 + sa.range * rng.nextDouble());
if (newIsVertical) {
newR = Math.min(Math.max(newR, 0), N - L[k] - 1);
newC = Math.min(Math.max(newC, 0), N - 1);
} else {
newR = Math.min(Math.max(newR, 0), N - 1);
newC = Math.min(Math.max(newC, 0), N - L[k] - 1);
}
double deltaScore = 0;

if (currentIsVertical) {
for (int l = 0; l < L[k]; l++) {
if (A[currentR + l][currentC] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
} else {
for (int l = 0; l < L[k]; l++) {
if (A[currentR][currentC + l] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}
if (newIsVertical) {
for (int l = 0; l < L[k]; l++) {
if (isIntersect(newR + l, newC, currentR, currentC, currentR + (currentIsVertical ? L[k] - 1 : 0), currentC + (currentIsVertical ? 0 : L[k] - 1))) {
if (A[newR + l][newC] == 0) {
deltaScore++;
} else {
deltaScore--;
}
} else {
if (A[newR + l][newC] == 1) {
deltaScore++;
} else {
deltaScore--;
}
}
}
} else {
for (int l = 0; l < L[k]; l++) {
if (isIntersect(newR, newC + l, currentR, currentC, currentR + (currentIsVertical ? L[k] - 1 : 0), currentC + (currentIsVertical ? 0 : L[k] - 1))) {
if (A[newR][newC + l] == 0) {
deltaScore++;
} else {
deltaScore--;
}
} else {
if (A[newR][newC + l] == 1) {
deltaScore++;
} else {
deltaScore--;
}
}
}
}

if (sa.accept(deltaScore)) {
score += deltaScore;

flip(k, currentIsVertical, currentR, currentC);
flip(k, newIsVertical, newR, newC);

isVerticals[k] = newIsVertical;
rs[k] = newR;
cs[k] = newC;

saveBest();
} else {
}
}

private void swap() {
int k = (int) (K * rng.nextDouble());
int k2 = (int) (K * rng.nextDouble());
while (L[k] == L[k2] || Math.abs(L[k] - L[k2]) > 5) {
k2 = (int) (K * rng.nextDouble());
}

if (L[k] > L[k2]) {
if (isVerticals[k2]) {
if (rs[k2] + L[k] >= N) {
return;
}
} else {
if (cs[k2] + L[k] >= N) {
return;
}
}
} else {
if (isVerticals[k]) {
if (rs[k] + L[k2] >= N) {
return;
}
} else {
if (cs[k] + L[k2] >= N) {
return;
}
}
}
double deltaScore = 0;

if (L[k] > L[k2]) {
if (isVerticals[k]) {
for (int l = L[k2]; l < L[k]; l++) {
if (A[rs[k] + l][cs[k]] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
} else {
for (int l = L[k2]; l < L[k]; l++) {
if (A[rs[k]][cs[k] + l] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}

if (isVerticals[k2]) {
for (int l = L[k2]; l < L[k]; l++) {
if (isIntersect(rs[k2] + l, cs[k2], rs[k] + (isVerticals[k] ? L[k2] : 0), cs[k] + (isVerticals[k] ? 0 : L[k2]), rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) {
if (A[rs[k2] + l][cs[k2]] == 1) {
deltaScore--;
} else {
deltaScore++;
}
} else {
if (A[rs[k2] + l][cs[k2]] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}
} else {
for (int l = L[k2]; l < L[k]; l++) {
if (isIntersect(rs[k2], cs[k2] + l, rs[k] + (isVerticals[k] ? L[k2] : 0), cs[k] + (isVerticals[k] ? 0 : L[k2]), rs[k] + (isVerticals[k] ? L[k] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k] - 1))) {
if (A[rs[k2]][cs[k2] + l] == 1) {
deltaScore--;
} else {
deltaScore++;
}
} else {
if (A[rs[k2]][cs[k2] + l] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}
}
} else {
if (isVerticals[k]) {
for (int l = L[k]; l < L[k2]; l++) {
if (A[rs[k] + l][cs[k]] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
} else {
for (int l = L[k]; l < L[k2]; l++) {
if (A[rs[k]][cs[k] + l] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}

if (isVerticals[k2]) {
for (int l = L[k]; l < L[k2]; l++) {
if (isIntersect(rs[k2] + l, cs[k2], rs[k] + (isVerticals[k] ? L[k] : 0), cs[k] + (isVerticals[k] ? 0 : L[k]), rs[k] + (isVerticals[k] ? L[k2] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k2] - 1))) {
if (A[rs[k2] + l][cs[k2]] == 1) {
deltaScore--;
} else {
deltaScore++;
}
} else {
if (A[rs[k2] + l][cs[k2]] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}
} else {
for (int l = L[k]; l < L[k2]; l++) {
if (isIntersect(rs[k2], cs[k2] + l, rs[k] + (isVerticals[k] ? L[k] : 0), cs[k] + (isVerticals[k] ? 0 : L[k]), rs[k] + (isVerticals[k] ? L[k2] - 1 : 0), cs[k] + (isVerticals[k] ? 0 : L[k2] - 1))) {
if (A[rs[k2]][cs[k2] + l] == 1) {
deltaScore--;
} else {
deltaScore++;
}
} else {
if (A[rs[k2]][cs[k2] + l] == 0) {
deltaScore--;
} else {
deltaScore++;
}
}
}
}
}
if (sa.accept(deltaScore)) {
score += deltaScore;
if (L[k] > L[k2]) {
if (isVerticals[k]) {
for (int l = L[k2]; l < L[k]; l++) {
A[rs[k] + l][cs[k]] ^= 1;
}
} else {
for (int l = L[k2]; l < L[k]; l++) {
A[rs[k]][cs[k] + l] ^= 1;
}
}

if (isVerticals[k2]) {
for (int l = L[k2]; l < L[k]; l++) {
A[rs[k2] + l][cs[k2]] ^= 1;
}
} else {
for (int l = L[k2]; l < L[k]; l++) {
A[rs[k2]][cs[k2] + l] ^= 1;
}
}
} else {
if (isVerticals[k]) {
for (int l = L[k]; l < L[k2]; l++) {
A[rs[k] + l][cs[k]] ^= 1;
}
} else {
for (int l = L[k]; l < L[k2]; l++) {
A[rs[k]][cs[k] + l] ^= 1;
}
}

if (isVerticals[k2]) {
for (int l = L[k]; l < L[k2]; l++) {
A[rs[k2] + l][cs[k2]] ^= 1;
}
} else {
for (int l = L[k]; l < L[k2]; l++) {
A[rs[k2]][cs[k2] + l] ^= 1;
}
}
}

{
boolean swap = isVerticals[k];
isVerticals[k] = isVerticals[k2];
isVerticals[k2] = swap;
}
{
int swap = rs[k];
rs[k] = rs[k2];
rs[k2] = swap;
swap = cs[k];
cs[k] = cs[k2];
cs[k2] = swap;
}
saveBest();
} else {
}
}

private void move() {
int k = (int) (K * rng.nextDouble());

double deltaScoreRorD = 0;

if (isVerticals[k]) {
if (rs[k] + L[k] >= N) {
deltaScoreRorD = Double.NEGATIVE_INFINITY;
}
} else {
if (cs[k] + L[k] >= N) {
deltaScoreRorD = Double.NEGATIVE_INFINITY;
}
}

if (deltaScoreRorD > -1) {
if (A[rs[k]][cs[k]] == 0) {
deltaScoreRorD--;
} else {
deltaScoreRorD++;
}
if (isVerticals[k]) {
if (A[rs[k] + L[k]][cs[k]] == 0) {
deltaScoreRorD--;
} else {
deltaScoreRorD++;
}
} else {
if (A[rs[k]][cs[k] + L[k]] == 0) {
deltaScoreRorD--;
} else {
deltaScoreRorD++;
}
}
}

double deltaScoreLorU = 0;

if (isVerticals[k]) {
if (rs[k] - 1 < 0) {
deltaScoreLorU = Double.NEGATIVE_INFINITY;
}
} else {
if (cs[k] - 1 < 0) {
deltaScoreLorU = Double.NEGATIVE_INFINITY;
}
}

if (deltaScoreLorU > -1) {
if (isVerticals[k]) {
if (A[rs[k] - 1][cs[k]] == 0) {
deltaScoreLorU--;
} else {
deltaScoreLorU++;
}
if (A[rs[k] + L[k] - 1][cs[k]] == 0) {
deltaScoreLorU--;
} else {
deltaScoreLorU++;
}
} else {
if (A[rs[k]][cs[k] - 1] == 0) {
deltaScoreLorU--;
} else {
deltaScoreLorU++;
}
if (A[rs[k]][cs[k] + L[k] - 1] == 0) {
deltaScoreLorU--;
} else {
deltaScoreLorU++;
}
}
}

double deltaScore = Math.max(deltaScoreRorD, deltaScoreLorU);

if (sa.accept(deltaScore)) {
score += deltaScore;
if (deltaScoreRorD > deltaScoreLorU) {
if (isVerticals[k]) {
A[rs[k]][cs[k]] ^= 1;
A[rs[k] + L[k]][cs[k]] ^= 1;
rs[k]++;
} else {
A[rs[k]][cs[k]] ^= 1;
A[rs[k]][cs[k] + L[k]] ^= 1;
cs[k]++;
}
} else {
if (isVerticals[k]) {
A[rs[k] - 1][cs[k]] ^= 1;
A[rs[k] + L[k] - 1][cs[k]] ^= 1;
rs[k]--;
} else {
A[rs[k]][cs[k] - 1] ^= 1;
A[rs[k]][cs[k] + L[k] - 1] ^= 1;
cs[k]--;
}
}
saveBest();
} else {
}
}

private String makeSolution() {
StringBuilder result = new StringBuilder();
for (int k = 0; k < K; k++) {
if (isVerticals[k]) {
result.append("" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1 + (L[k] - 1)) + " " + (cs[k] + 1) + "\\n");
} else {
result.append("" + (rs[k] + 1) + " " + (cs[k] + 1) + " " + (rs[k] + 1) + " " + (cs[k] + 1 + (L[k] - 1)) + "\\n");
}
}
return result.toString();
}

private boolean isIntersect(int r, int c, int minR, int minC, int maxR, int maxC) {
return r >= minR && r <= maxR && c >= minC && c <= maxC;
}

private void flip(int k, boolean isVertical, int r, int c) {
if (isVertical) {
for (int l = 0; l < L[k]; l++) {
A[r + l][c] ^= 1;
}
} else {
for (int l = 0; l < L[k]; l++) {
A[r][c + l] ^= 1;
}
}
}

private int calculateScore(int[][] a) {
int W = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (a[r][c] == 0) {
W++;
}
}
}
return W - W0;
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int k = 0; k < K; k++) {
bestIsVerticals[k] = isVerticals[k];
bestRs[k] = rs[k];
bestCs[k] = cs[k];
}
}
}

private void loadBest() {
score = bestScore;
for (int k = 0; k < K; k++) {
isVerticals[k] = bestIsVerticals[k];
rs[k] = bestRs[k];
cs[k] = bestCs[k];
}
}
}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.5;
public double time = startTime;

public double startTemperature = 1;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;
public double startRange = 31;
public double endRange = 3;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? Main.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 ? Main.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
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;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

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

}



Rank 暫定30位くらい


Approach

  • submission1
    • Approach : ジャンクション無しで MST
    • 同点で並んでいるところに混ざりたかったのに失敗した。
  • submission2
    • Score : 0.5%ほど改善
    • Approach : SA
    • 近傍 : ジャンクションを加える、外す
    • 複数の点の位置を決める問題なのでSAでいいでしょう。
  • submission3
    • Score : 0.1%ほど改善
    • Approach : SA
    • Kruskalの高速化 : 都市x都市の辺を並べ替えて覚えておく。計算するときに、都市xジャンクションとジャンクションxジャンクションの辺を生成して、並べ替えて、 マージソートのようにして、距離の短い辺を取り出す。
    • スコアの近似 : 使えるジャンクションはランダムに選ばれるので、期待値を使いたい。でも遅いので近似することにする。期待値の近似 : ジャンクションのコスト*ジャンクション数 + ジャンクション無しのMST + (1 - ジャンクションの失敗率) * (ジャンクション有りのMST - ジャンクション無しのMST)
    • スコアの近似は最小二乗法(特徴は{ジャンクションコスト、失敗率、S、都市数、ジャンクション数、ジャンクション無しのMST、ジャンクション有りのMST、ジャンクションコスト*失敗率、ジャンクションコスト*S、...、ジャンクション無しのMST*ジャンクション有りのMST})も使ったけど、ほぼ同じ式になった。
  • submission4
    • Score : 0.05%ほど改善
    • Approach : SA
    • 近傍 : ジャンクションを加える、外す、移動する
  • submission5
    • Score : 0.05%ほど改善
    • Approach : SA
    • Kruskalの高速化 : 都市x都市の辺を並べ替えて覚えておく。使わない辺を除くいておく。


source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class RoadsAndJunctions {
	private int numCities;
	private Point[] cities;
	private double junctionCost;
	private double failureProbability;
	private int S;

	static final XorShift rng = new XorShift(System.nanoTime());
	static final Watch watch = new Watch();
	private SAState sa = new SAState();

	private double score;
	private int numJunctions;
	private Point[] junctions;

	private double bestScore;
	private int numBestJunctions;
	private Point[] bestJunctions;

	private UnionFind unionFind;

	private Comparator comparator = new Comparator() {
		@Override
		public int compare(Edge2 o1, Edge2 o2) {
			if (o1.cost < o2.cost) {
				return -1;
			}
			if (o1.cost > o2.cost) {
				return 1;
			}
			return 0;
		}
	};

	private int numEdges;
	private Edge2[] edges;
	private int numNewEdges;
	private Edge2[] newEdges;
	private double baseScore;
	private double time;

	public int[] buildJunctions(int S, int[] cities, double junctionCost, double failureProbability) {
		init(S, cities, junctionCost, failureProbability);
		solve();
		int[] makeSolution = makeSolution();
		time = watch.getSecond();
		Utils.debug("score", score, "time", time);
		return makeSolution;
	}

	private void init(int S, int[] cities, double junctionCost, double failureProbability) {
		watch.init();

		this.S = S;

		numCities = cities.length / 2;
		this.cities = new Point[numCities];
		for (int i = 0; i < this.cities.length; i++) {
			this.cities[i] = new Point(cities[2 * i + 1], cities[2 * i + 0]);
		}

		this.junctionCost = junctionCost;
		this.failureProbability = failureProbability;

		numJunctions = 0;
		junctions = new Point[2 * numCities];
		for (int i = 0; i < junctions.length; i++) {
			junctions[i] = new Point(0, 0);
		}
		numBestJunctions = 0;
		bestJunctions = new Point[2 * numCities];
		for (int i = 0; i < bestJunctions.length; i++) {
			bestJunctions[i] = new Point(0, 0);
		}

		edges = new Edge2[3 * numCities * 3 * numCities];
		for (int i = 0; i < edges.length; i++) {
			edges[i] = new Edge2(0, 0, 0);
		}
		newEdges = new Edge2[3 * numCities * 3 * numCities];
		for (int i = 0; i < newEdges.length; i++) {
			newEdges[i] = new Edge2(0, 0, 0);
		}

		for (int from = 0; from < numCities; from++) {
			for (int to = from + 1; to < numCities; to++) {
				edges[numEdges].from = from;
				edges[numEdges].to = to;
				edges[numEdges].cost = distance(from, to);
				numEdges++;
			}
		}
		Arrays.sort(edges, 0, numEdges, comparator);

		unionFind = new UnionFind(2 * numCities);

		{
			unionFind.init(numCities);

			double cost = 0;
			int numEdges2 = 0;
			for (int i = 0; i < numEdges; i++) {
				Edge2 edge2 = edges[i];

				if (unionFind.isSame(edge2.from, edge2.to)) {
					for (int j = i; j < numEdges - 1; j++) {
						edges[j] = edges[j + 1];
					}
					numEdges--;
					i--;
					continue;
				}
				unionFind.unite(edge2.from, edge2.to);

				cost += edge2.cost;
				numEdges2++;
				if (numEdges2 >= numCities - 1) {
					numEdges = i + 1;
					break;
				}

			}
			assert numEdges == numEdges2;
			score = cost;
		}
		baseScore = score;

		bestScore = 1e9;
		saveBest();

		Utils.debug("S", S, "numCities", numCities, "cost", String.format("%.1f", junctionCost), "probability", String.format("%.1f%%", 100.0 * failureProbability));
	}

	private double kruskal(Point[] junctions, int numJunctions) {
		int numVertexes = numCities + numJunctions;

		unionFind.init(numVertexes);
		numNewEdges = 0;
		for (int from = numCities; from < numCities + numJunctions; from++) {
			for (int to = 0; to < from; to++) {
				double cost = distance(from, to);
				if (cost <= edges[numEdges - 1].cost) {
					newEdges[numNewEdges].from = from;
					newEdges[numNewEdges].to = to;
					newEdges[numNewEdges].cost = cost;
					numNewEdges++;
				}
			}
		}
		Arrays.sort(newEdges, 0, numNewEdges, comparator);

		double cost = 0;
		int numEdges = 0;
		for (int i = 0, i2 = 0; i < this.numEdges || i2 < numNewEdges;) {
			Edge2 edge2;
			if (i >= this.numEdges) {
				edge2 = newEdges[i2++];
			} else if (i2 >= numNewEdges) {
				edge2 = edges[i++];
			} else if (edges[i].cost <= newEdges[i2].cost) {
				edge2 = edges[i++];
			} else {
				edge2 = newEdges[i2++];
			}

			if (unionFind.isSame(edge2.from, edge2.to)) {
				continue;
			}
			unionFind.unite(edge2.from, edge2.to);

			cost += edge2.cost;
			numEdges++;
			if (numEdges >= numVertexes - 1) {
				break;
			}
		}

		return cost;
	}

	private void solve() {
		SA();
		sortJunctions();
	}

	private void sortJunctions() {
		MinimumSpanningTree mst = new MinimumSpanningTree(numCities + numJunctions);
		for (int from = 0; from < numCities + numJunctions; from++) {
			for (int to = from + 1; to < numCities + numJunctions; to++) {
				mst.addEdge(from, to, distance(from, to));
			}
		}
		mst.kruskal();

		ArrayList> hashAndPointPairs = new ArrayList<>();
		for (int from = numCities; from < numCities + numJunctions; from++) {
			ArrayList edges = mst.G.get(from);
			int[] indexes = new int[edges.size()];
			for (int i = 0; i < indexes.length; i++) {
				indexes[i] = edges.get(i).to;
			}
			Arrays.sort(indexes);
			int hashCode = hashCode(indexes);
			hashAndPointPairs.add(new Pair<>(hashCode, new Point(junctions[from - numCities].r, junctions[from - numCities].c)));
		}
		Collections.sort(hashAndPointPairs);

		numJunctions = 0;
		for (Pair pair : hashAndPointPairs) {
			junctions[numJunctions].r = pair.second.r;
			junctions[numJunctions].c = pair.second.c;
			numJunctions++;
		}

	}

	private int hashCode(int a[]) {
		int result = 1;
		for (int element : a) {
			result = 131 * result + element;
		}
		return result;
	}

	private void SA() {
		double second = Math.ceil(watch.getSecond());

		sa.startTime = watch.getSecond();
		sa.endTime = 9.5;
		sa.init();
		for (;; sa.numIterations++) {
			if ((sa.numIterations & ((1 << 8) - 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));
					Utils.debug("score", score, "" + (score - numJunctions * junctionCost) + " + " + junctionCost + " * " + numJunctions + "");
					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();
		}
	}

	private void mutate() {
		int random = (int) (3 * rng.nextDouble());
		if (random == 0) {
			add();
		} else if (random == 1) {
			remove();
		} else if (random == 2) {
			move();
		}
	}

	private void add() {
		if (numJunctions >= 2 * numCities) {
			return;
		}
		int r = (int) (S * rng.nextDouble());
		int c = (int) (S * rng.nextDouble());
		junctions[numJunctions].r = r;
		junctions[numJunctions].c = c;
		numJunctions++;

		double deltaScore = calculateApproximateExpectedScore() - score;
		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			numJunctions--;
		}
	}

	private void remove() {
		if (numJunctions == 0) {
			return;
		}

		int index = (int) (numJunctions * rng.nextDouble());
		{
			Point swap = junctions[index];
			junctions[index] = junctions[numJunctions - 1];
			junctions[numJunctions - 1] = swap;
		}

		numJunctions--;
		double deltaScore = calculateApproximateExpectedScore() - score;

		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			numJunctions++;
		}
	}

	private void move() {
		if (numJunctions == 0) {
			return;
		}

		Point point = junctions[(int) (numJunctions * rng.nextDouble())];

		int currentR = point.r;
		int currentC = point.c;

		point.r += -(int) (0.5 * sa.range) + (sa.range * rng.nextDouble());
		point.c += -(int) (0.5 * sa.range) + (sa.range * rng.nextDouble());

		double deltaScore = calculateApproximateExpectedScore() - score;

		if (sa.accept(deltaScore)) {
			score += deltaScore;
			saveBest();
		} else {
			point.r = currentR;
			point.c = currentC;
		}
	}

	private double calculateApproximateExpectedScore() {
		double score = kruskal(junctions, numJunctions);
		return junctionCost * numJunctions + baseScore + (1.0 - failureProbability) * (score - baseScore);
	}

	private int[] makeSolution() {
		int[] solution = new int[2 * numJunctions];
		for (int i = 0; i < numJunctions; i++) {
			solution[2 * i + 0] = junctions[i].c;
			solution[2 * i + 1] = junctions[i].r;
		}
		return solution;
	}

	public int[] buildRoads(int[] junctionStatus) {
		watch.init();

		int validJunctions = 0;
		boolean[] canUse = new boolean[junctionStatus.length];
		for (int i = 0; i < canUse.length; i++) {
			canUse[i] = junctionStatus[i] == 1;
			if (canUse[i]) {
				validJunctions++;
			}
		}

		Utils.debug("validJunctions", validJunctions, "numJunctions", numJunctions);

		MinimumSpanningTree mst = new MinimumSpanningTree(numCities + numJunctions);
		for (int from = 0; from < numCities; from++) {
			for (int to = from + 1; to < numCities; to++) {
				mst.addEdge(from, to, distance(from, to));
			}
			for (int to = numCities; to < numCities + numJunctions; to++) {
				if (!canUse[to - numCities]) {
					continue;
				}
				mst.addEdge(from, to, distance(from, to));
			}
		}
		for (int from = numCities; from < numCities + numJunctions; from++) {
			if (!canUse[from - numCities]) {
				continue;
			}
			for (int to = from + 1; to < numCities + numJunctions; to++) {
				if (!canUse[to - numCities]) {
					continue;
				}
				mst.addEdge(from, to, distance(from, to));
			}
		}

		score = mst.kruskal();
		Utils.debug("score", score + numJunctions * junctionCost, "" + score + " + " + junctionCost + " * " + numJunctions + "");
		score += junctionCost * numJunctions;

		int[] ret = new int[2 * (numCities + validJunctions - 1)];
		int reti = 0;

		LinkedList queue = new LinkedList<>();
		boolean[] used = new boolean[numCities + numJunctions];
		{
			int current = 0;
			queue.add(current);
			used[current] = true;
		}
		for (; !queue.isEmpty();) {
			int current = queue.poll().intValue();
			ArrayList edges = mst.G.get(current);
			for (int i = 0; i < edges.size(); i++) {
				int next = edges.get(i).to;
				if (used[next]) {
					continue;
				}
				used[next] = true;
				queue.add(next);
				ret[2 * reti + 0] = current;
				ret[2 * reti + 1] = next;
				reti++;
			}
		}

		time += watch.getSecond();
		Utils.debug("score", score, "time", time);
		return ret;
	}

	private double distance(int from, int to) {
		int dr = getR(from) - getR(to);
		int dc = getC(from) - getC(to);
		return Math.sqrt(dr * dr + dc * dc);
	}

	private double distance(Point from, Point to) {
		int dr = from.r - to.r;
		int dc = from.c - to.c;
		return Math.sqrt(dr * dr + dc * dc);
	}

	private Point getPoint(int index) {
		return index < numCities ? cities[index] : junctions[index - numCities];
	}

	private int getR(int index) {
		return getPoint(index).r;
	}

	private int getC(int index) {
		return getPoint(index).c;
	}

	private void saveBest() {
		if (score < bestScore) {
			bestScore = score;
			numBestJunctions = 0;
			for (int i = 0; i < numJunctions; i++) {
				bestJunctions[numBestJunctions].r = junctions[i].r;
				bestJunctions[numBestJunctions].c = junctions[i].c;
				numBestJunctions++;
			}
		}
	}

	private void loadBest() {
		score = bestScore;
		numJunctions = 0;
		for (int i = 0; i < numBestJunctions; i++) {
			junctions[numJunctions].r = bestJunctions[i].r;
			junctions[numJunctions].c = bestJunctions[i].c;
			numJunctions++;
		}
	}

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

			int S = Integer.parseInt(br.readLine());
			int C = Integer.parseInt(br.readLine());
			int[] cities = new int[C];
			for (int i = 0; i < C; ++i) {
				cities[i] = Integer.parseInt(br.readLine());
			}
			double junctionCost = Double.parseDouble(br.readLine());
			double failureProbability = Double.parseDouble(br.readLine());

			RoadsAndJunctions rj = new RoadsAndJunctions();
			int[] ret = rj.buildJunctions(S, cities, junctionCost, failureProbability);
			System.out.println(ret.length);
			for (int i = 0; i < ret.length; ++i) {
				System.out.println(ret[i]);
			}
			System.out.flush();

			int J = Integer.parseInt(br.readLine());
			int[] junctionStatus = new int[J];
			for (int i = 0; i < J; ++i) {
				junctionStatus[i] = Integer.parseInt(br.readLine());
			}
			ret = rj.buildRoads(junctionStatus);
			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 Point {
	int r;
	int c;

	public Point(int r, int c) {
		this.r = r;
		this.c = c;
	}

	public boolean equals(Point other) {
		return (r == other.r && c == other.c);
	}

	public int dist2(Point other) {
		return (r - other.r) * (r - other.r) + (c - other.c) * (c - other.c);
	}

}

class MinimumSpanningTree {

	private static final int INF = (int) 1e9;
	ArrayList> G;
	private ArrayList edges;
	private int numVertexes;

	public MinimumSpanningTree(int v) {
		clear(v);
	}

	public void clear(int v) {
		this.numVertexes = v;

		G = new ArrayList>();
		for (int i = 0; i < v; i++) {
			G.add(new ArrayList());
		}
		edges = new ArrayList();
	}

	public void addEdge(int from, int to, double cost) {
		assert cost >= 0;
		assert cost <= INF;
		edges.add(new Edge2(from, to, cost));
	}

	public double kruskal() {
		UnionFind unionFind = new UnionFind(numVertexes);
		unionFind.init(numVertexes);

		Collections.sort(edges, new Comparator() {
			@Override
			public int compare(Edge2 o1, Edge2 o2) {
				if (o1.cost < o2.cost) {
					return -1;
				}
				if (o1.cost > o2.cost) {
					return 1;
				}
				return 0;
			}
		});

		double cost = 0;
		int numEdges = 0;
		for (Edge2 edge2 : edges) {
			if (unionFind.isSame(edge2.from, edge2.to)) {
				continue;
			}
			unionFind.unite(edge2.from, edge2.to);

			G.get(edge2.from).add(new Edge(edge2.to, edge2.cost));
			G.get(edge2.to).add(new Edge(edge2.from, edge2.cost));

			cost += edge2.cost;
			numEdges++;
			if (numEdges >= numVertexes - 1) {
				break;
			}
		}
		return cost;
	}

	public int prim() {

		ArrayList> G = new ArrayList<>();
		for (int i = 0; i < numVertexes; i++) {
			G.add(new ArrayList<>());
		}
		for (Edge2 edge2 : edges) {
			G.get(edge2.from).add(new Edge2(edge2.from, edge2.to, edge2.cost));
			G.get(edge2.to).add(new Edge2(edge2.to, edge2.from, edge2.cost));
		}

		int cost = 0;
		int numEdges = 0;

		boolean[] used = new boolean[numVertexes];
		PriorityQueue pq = new PriorityQueue<>(new Comparator() {
			@Override
			public int compare(Edge2 o1, Edge2 o2) {
				if (o1.cost < o2.cost) {
					return -1;
				}
				if (o1.cost > o2.cost) {
					return 1;
				}
				return 0;
			}
		});
		{
			int vertex = (int) (numVertexes * Math.random());
			pq.add(new Edge2(vertex, vertex, 0));
		}
		for (; !pq.isEmpty();) {
			Edge2 current = pq.poll();

			if (used[current.to]) {
				continue;
			}

			used[current.to] = true;
			cost += current.cost;

			if (current.from != current.to) {
				numEdges++;
				if (numEdges == numVertexes - 1) {
					break;
				}

				this.G.get(current.from).add(new Edge(current.to, current.cost));
				this.G.get(current.to).add(new Edge(current.from, current.cost));
			}

			for (Edge2 edge : G.get(current.to)) {
				if (used[edge.to]) {
					continue;
				}
				pq.add(edge);
			}

		}

		return cost;
	}

}

class Edge {
	int to;
	double cost;

	public Edge(int to, double cost) {
		this.to = to;
		this.cost = cost;
	}
}

class Edge2 {
	int from;
	int to;
	double cost;

	public Edge2(int from, int to, double cost) {
		this.from = from;
		this.to = to;
		this.cost = cost;
	}
}

class SAState {

	public static final boolean useTime = true;

	public double startTime = 0;
	public double endTime = 9.5;
	public double time = startTime;

	public double startTemperature = 1;
	public double endTemperature = 0;
	public double inverseTemperature = 1.0 / startTemperature;
	public double lastAcceptTemperature = startTemperature;

	public double startRange = 101;
	public double endRange = 3;
	public double range = startRange;

	public int numIterations;
	public int validIterations;
	public int acceptIterations;

	public void init() {
		numIterations = 0;
		validIterations = 0;
		acceptIterations = 0;

		startTime = useTime ? RoadsAndJunctions.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 ? RoadsAndJunctions.watch.getSecond() : numIterations;
	}

	public boolean isTLE() {
		return time >= endTime;
	}

	public boolean accept(double deltaScore) {
		return acceptS(deltaScore);
	}

	public boolean acceptB(double deltaScore) {
		validIterations++;

		if (deltaScore > -1e-9) {
			acceptIterations++;
			return true;
		}

		assert deltaScore < 0;
		assert 1.0 / inverseTemperature >= 0;

		if (deltaScore * inverseTemperature < -10) {
			return false;
		}

		if (RoadsAndJunctions.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
			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;

		if (-deltaScore * inverseTemperature < -10) {
			return false;
		}

		if (RoadsAndJunctions.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 UnionFind {
	private int[] par;
	private int[] rank;

	public UnionFind(int capacity) {
		par = new int[capacity];
		rank = new int[capacity];
	}

	public void init(int n) {
		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	public int getRoot(int x) {
		if (par[x] == x) {
			return x;
		} else {
			par[x] = getRoot(par[x]);
			return par[x];
		}
	}

	public void unite(int x, int y) {
		x = getRoot(x);
		y = getRoot(y);
		if (x == y) {
			return;
		}
		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y]) {
				rank[x]++;
			}
		}
	}

	public boolean isSame(int x, int y) {
		return getRoot(x) == getRoot(y);
	}
}

class Pair, S> implements Comparable> {
	public T first;
	public S second;

	public Pair(T t, S s) {
		this.first = t;
		this.second = s;
	}

	private int hash = 0;

	@Override
	public int hashCode() {
		if (hash == 0) {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((first == null) ? 0 : first.hashCode());
			result = prime * result + ((second == null) ? 0 : second.hashCode());
			hash = result;
		}
		return hash;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Pair other = (Pair) obj;
		if (first == null) {
			if (other.first != null)
				return false;
		} else if (!first.equals(other.first))
			return false;
		if (second == null) {
			if (other.second != null)
				return false;
		} else if (!second.equals(other.second))
			return false;
		return true;
	}

	@Override
	public int compareTo(Pair o) {
		return first.compareTo(o.first);
	}
}



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

}



このページのトップヘ