EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

April 2018



Score and Approach
  • submission1
    • ランダムプレイアウト
    • ローカルの平均 : 0.965
    • 何もしていないのにいいスコアが出た。と思っていたら130位くらいまで落ちた。
  • submission2
    • 多スタート + ランダムプレイアウト
    • ローカルの平均 : 0.994
    • 時間が余っていたので多スタートにする。
  • submission3
    • SA + ランダムプレイアウト
    • ローカルの平均 : 0.9973
    • 最初から全部やり直す必要はないなと思ったので、途中まで戻して、そこからランダムプレイアウトするSAにする。ここまでハイレベルのアプローチを強いものに変えていくことで順調に改善する。
  • submission4
    • 近傍を改善したSA + ランダムプレイアウト
    • ローカルの平均 : 0.9978
    • 途中まで戻していく時に、現在の解で消せてない場所を消せないか試して、1っ箇所消せたらそこからランダムプレイアウトするSAにする。全部消せる確率が上がった。
  • submission5
    • スコアがバラつくので同じ解を提出。順位も思ったより変わった。
  • submission6
    • 2つの近傍を使うSA + ランダムプレイアウト
    • ローカルの平均 : 0.9989
    • submission4の近傍と、途中まで戻して、現在の解で消せてない場所を消せないか試しながら、できるだけ現在の解を再現するようにする、という近傍を加える。
    • このあたりでchokudai search を試すもスコアはSAの方が良かった。beam search は盤面をどう評価していいかわからなかったので、試せなかった。
  • submission7
    • パラメータチューニングした2つの近傍を使うSA + ランダムプレイアウト
    • ローカルの平均 : 0.9992
    • 多スタートにしたり、温度を変えて、パラメータチューニングした。
  • submission8
    • さらにパラメータチューニングした2つの近傍を使うSA + ランダムプレイアウト
    • ローカルの平均 : 0.9993
    • 多スタートをやめたり、温度を変えて、パラメータチューニングした。


source code

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

public class SameColorPairs {
	private static final int[] dr = new int[] { -1, 0, 0, 1, };
	private static final int[] dc = new int[] { 0, -1, 1, 0, };
	private static final int EMPTY = -1;

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

	private int H;
	private int W;
	private int[][] board;
	private int numColors;
	private int best;
	private int[] bestHistory;

	private long hash;
	private long[][] hashes;

	private SAState sa = new SAState();
	private HashSet usedHash = new HashSet<>();

	private int[] currentHistory;
	private int bestTurn;
	private int numDeplications;

	private int[] solution;
	private int usedSize;
	private int[] bestSolution;
	private int[] solutionToIndex;
	private int numEmptys;
	private int numValids;

	public String[] removePairs(String[] board) {
		init(board);
		solve();
		Utils.debug("numDeplications", numDeplications, "usedHash.size()", usedHash.size(), "numNexts", numNexts, "numEmptys", numEmptys, "numValids", numValids);
		return makeResult();
	}

	private void init(String[] _board) {
		H = _board.length;
		W = _board[0].length();

		board = new int[H][W];
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				board[r][c] = (_board[r].charAt(c) - '0');
			}
		}

		numColors = 0;
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				numColors = Math.max(numColors, board[r][c] + 1);
			}
		}

		best = -1;

		history = new int[H * W / 2];
		bestHistory = new int[H * W / 2];

		used = new int[H][W];

		queue = new int[H * W];
		currentHistory = new int[H * W / 2];

		hash = 0;
		hashes = new long[H][W];
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				hashes[r][c] = rng.nextLong();
			}
		}

		usedSize = 0;
		solution = new int[H * W];
		solutionToIndex = new int[H * W];
		bestSolution = new int[H * W];
		for (int i = 0; i < solution.length; i++) {
			solution[i] = i;
			bestSolution[i] = i;
		}
		for (int i = 0; i < solutionToIndex.length; i++) {
			solutionToIndex[solution[i]] = i;
		}
		for (int i = 0; i < solutionToIndex.length; i++) {
			assert solution[solutionToIndex[i]] == i;
			assert solutionToIndex[solution[i]] == i;
		}
		Utils.debug("H", H, "W", W, "H*W", H * W, "numColors", numColors);
	}

	private void solve() {
		SA();
		Utils.debug("time", watch.getSecondString(), "score", best + "/" + (H * W), best * 1.0 / (H * W));
	}

	private void saveBest() {
		if (numRemoved > best) {
			best = numRemoved;
			bestTurn = turn;
			System.arraycopy(history, 0, bestHistory, 0, turn);
		}
	}

	private void SA() {
		double second = Math.ceil(watch.getSecond());
		sa.init();
		for (;; sa.numIterations++) {
			{
				sa.updateTime();

				if (best == (H * W) || sa.isTLE()) {
					Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%5d", numRemoved), String.format("%5d", best), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
					break;
				}

				sa.updateTemperature();
				sa.updateRange();

				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("%5d", numRemoved), String.format("%5d", best), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "numResultEmpty", numEmptys, "numResultValid", numValids);
				}
			}

			change();
		}
	}

	private boolean first = true;

	private void change() {
		if (first || rng.nextDouble() < 0.5) {
			first = false;
			random();
		} else {
			insert();
		}
	}

	private void insert() {
		int randomTurn = (int) (turn * rng.nextDouble());
		System.arraycopy(history, 0, currentHistory, 0, turn);
		int currentNumRemoved = numRemoved;
		int currentTurn = turn;

		ArrayList cantRemoved = new ArrayList<>();
		for (int i = usedSize; i < solution.length; i++) {
			cantRemoved.add(solution[i]);
		}
		if (cantRemoved.size() == 0) {
			return;
		}

		for (; turn > randomTurn;) {
			previous();
		}
		for (int t = turn; t < currentTurn;) {
			for (int i = 0; i < cantRemoved.size(); i++) {
				int v = cantRemoved.get(i).intValue();
				int r = v / W;
				int c = v % W;
				if (board[r][c] == EMPTY) {
					continue;
				}
				int result = calculateMinDistanceSameColorPair(r, c);
				if (result == -1) {
					continue;
				}
				int r2 = (result >>> 16) & ((1 << 16) - 1);
				int c2 = (result >>> 0) & ((1 << 16) - 1);
				next(r, c, r2, c2);
				cantRemoved.remove(i);
				i--;
			}

			int v = currentHistory[t++];
			int r = (v >>> 21) & 127;
			int c = (v >>> 14) & 127;
			int r2 = (v >>> 7) & 127;
			int c2 = (v >>> 0) & 127;
			if (board[r][c] != EMPTY && board[r2][c2] != EMPTY && canRemove(r, c, r2, c2)) {
				next(r, c, r2, c2);
			} else {
				continue;
			}
		}

		randomPlayout();

		double deltaScore = numRemoved - currentNumRemoved;

		sa.validIterations++;
		if (deltaScore > -1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) {
			sa.acceptIterations++;
			if (!(deltaScore > -1e-9)) {
				sa.lastAcceptTemperature = sa.inverseTemperature;
			}

			saveBest();
		} else {
			for (; turn > randomTurn;) {
				previous();
			}
			for (; turn < currentTurn;) {
				int v = currentHistory[turn];
				int r = (v >>> 21) & 127;
				int c = (v >>> 14) & 127;
				int r2 = (v >>> 7) & 127;
				int c2 = (v >>> 0) & 127;
				next(r, c, r2, c2);
			}
		}
	}

	private boolean canRemove(int r1, int c1, int r2, int c2) {
		assert board[r1][c1] != EMPTY;
		assert board[r1][c1] == board[r2][c2];
		int minR = Math.min(r1, r2);
		int maxR = Math.max(r1, r2);
		int minC = Math.min(c1, c2);
		int maxC = Math.max(c1, c2);
		for (int r = minR; r <= maxR; r++) {
			for (int c = minC; c <= maxC; c++) {
				if (board[r][c] == EMPTY) {
					continue;
				}
				if (board[r][c] == board[r1][c1]) {
					continue;
				}
				return false;
			}
		}
		return true;
	}

	private void random() {
		int randomTurn = (int) (turn * rng.nextDouble());
		System.arraycopy(history, randomTurn, currentHistory, randomTurn, turn - randomTurn);
		int currentNumRemoved = numRemoved;
		int currentTurn = turn;

		ArrayList cantRemoved = new ArrayList<>();
		for (int r = 0; r < H; r++) {
			for (int c = 0; c < W; c++) {
				if (board[r][c] == EMPTY) {
					continue;
				}
				cantRemoved.add((r << 16) | (c));
			}
		}
		if (cantRemoved.size() == 0) {
			return;
		}

		turnLoop: for (; turn > randomTurn;) {
			previous();

			for (int i = 0; i < 3; i++) {
				int v = cantRemoved.get((int) (cantRemoved.size() * rng.nextDouble()));
				int r = (v >>> 16) & ((1 << 16) - 1);
				int c = (v >>> 0) & ((1 << 16) - 1);
				int result = calculateMinDistanceSameColorPair(r, c);
				if (result != -1) {
					randomTurn = turn;
					int r2 = (result >>> 16) & ((1 << 16) - 1);
					int c2 = (result >>> 0) & ((1 << 16) - 1);

					long nextHash = hash ^ hashes[r][c] ^ hashes[r2][c2];
					if (usedHash.add(nextHash)) {
						next(r, c, r2, c2);
						assert nextHash == hash;
					} else {
						numDeplications++;
						continue;
					}
					break turnLoop;
				}
			}
		}

		randomPlayout();

		double deltaScore = numRemoved - currentNumRemoved;

		sa.validIterations++;
		if (deltaScore > -1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) {
			sa.acceptIterations++;
			if (!(deltaScore > -1e-9)) {
				sa.lastAcceptTemperature = sa.inverseTemperature;
			}

			saveBest();
		} else {
			for (; turn > randomTurn;) {
				previous();
			}
			for (; turn < currentTurn;) {
				int v = currentHistory[turn];
				int r = (v >>> 21) & 127;
				int c = (v >>> 14) & 127;
				int r2 = (v >>> 7) & 127;
				int c2 = (v >>> 0) & 127;
				next(r, c, r2, c2);
			}
		}
	}

	private void randomPlayout() {
		for (;;) {
			shuffle(usedSize, solution.length, rng);
			boolean update = false;
			for (int i = usedSize; i < solution.length; i++) {
				int r = solution[i] / W;
				int c = solution[i] % W;
				if (board[r][c] == EMPTY) {
					continue;
				}
				int result = calculateMinDistanceSameColorPair(r, c);
				if (result == EMPTY) {
					numEmptys++;
					continue;
				}
				numValids++;
				int r2 = (result >>> 16) & ((1 << 16) - 1);
				int c2 = (result >>> 0) & ((1 << 16) - 1);

				long nextHash = hash ^ hashes[r][c] ^ hashes[r2][c2];
				if (usedHash.add(nextHash)) {
					next(r, c, r2, c2);
					assert nextHash == hash;
					update = true;
				} else {
					numDeplications++;
				}
			}

			if (!update) {
				break;
			}
		}
	}

	private void shuffle(int startInclusive, int endExclusive, XorShift rng) {
		for (int i = endExclusive - 1; i >= startInclusive; i--) {
			int j = startInclusive + (int) ((i + 1 - startInclusive) * rng.nextDouble());
			swap(i, j);
		}
	}

	private void swap(int i, int j) {
		int swap = solution[i];
		solution[i] = solution[j];
		solution[j] = swap;

		solutionToIndex[solution[i]] = i;
		solutionToIndex[solution[j]] = j;
	}

	private int numRemoved = 0;
	private int turn = 0;
	private int[] history;
	private int numNexts;

	private void next(int r, int c, int r2, int c2) {
		assert board[r][c] != EMPTY;
		assert board[r][c] == board[r2][c2];
		numNexts++;
		history[turn++] = (board[r][c] << 28) | (r << 21) | (c << 14) | (r2 << 7) | (c2);
		board[r][c] = EMPTY;
		board[r2][c2] = EMPTY;
		numRemoved += 2;
		hash ^= hashes[r][c] ^ hashes[r2][c2];
		swap(solutionToIndex[r * W + c], usedSize++);
		swap(solutionToIndex[r2 * W + c2], usedSize++);
	}

	private void previous() {
		int v = history[--turn];
		int color = (v >>> 28) & 15;
		int r = (v >>> 21) & 127;
		int c = (v >>> 14) & 127;
		int r2 = (v >>> 7) & 127;
		int c2 = (v >>> 0) & 127;
		board[r][c] = color;
		board[r2][c2] = color;
		numRemoved -= 2;
		hash ^= hashes[r][c] ^ hashes[r2][c2];
		usedSize -= 2;
	}

	private int[] queue;
	private int queueSize = 0;
	private int queueCurrent = 0;
	private int[][] used;
	private int numSearchs = 0;

	private int calculateMinDistanceSameColorPair(int r0, int c0) {
		numSearchs++;
		queueSize = 0;
		queueCurrent = 0;
		{
			queue[queueSize++] = ((r0 << 16) | (c0));
			used[r0][c0] = numSearchs;
		}
		for (; queueCurrent < queueSize;) {
			int v = queue[queueCurrent++];
			int r = (v >>> 16) & ((1 << 16) - 1);
			int c = (v >>> 0) & ((1 << 16) - 1);

			if (!(r == r0 && c == c0) && board[r][c] == board[r0][c0]) {
				return (r << 16) | (c);
			}
			for (int d = 0; d < dr.length; d++) {
				int nr = r + dr[d];
				int nc = c + dc[d];
				if (!isValid(nr, 0, H) || !isValid(nc, 0, W)) {
					continue;
				}
				if (used[nr][nc] == numSearchs) {
					continue;
				}
				if (board[nr][nc] != EMPTY && board[nr][nc] != board[r0][c0]) {
					continue;
				}

				if (nr > r0) {
					if (used[nr - 1][nc] == numSearchs) {

					} else {
						continue;
					}
				} else if (nr < r0) {
					if (used[nr + 1][nc] == numSearchs) {

					} else {
						continue;
					}
				}
				if (nc > c0) {
					if (used[nr][nc - 1] == numSearchs) {

					} else {
						continue;
					}
				} else if (nc < c0) {
					if (used[nr][nc + 1] == numSearchs) {

					} else {
						continue;
					}
				}

				used[nr][nc] = numSearchs;
				queue[queueSize++] = ((nr << 16) | (nc));
			}
		}
		return EMPTY;
	}

	private boolean isValid(int v, int min, int minUpperBound) {
		return v >= min && v < minUpperBound;
	}

	private String[] makeResult() {
		ArrayList pairs = new ArrayList();
		for (int t = 0; t < bestTurn; t++) {
			int v = bestHistory[t];
			int r = (v >>> 21) & 127;
			int c = (v >>> 14) & 127;
			int r2 = (v >>> 7) & 127;
			int c2 = (v >>> 0) & 127;
			pairs.add("" + r + " " + c + " " + r2 + " " + c2);
		}
		return (String[]) pairs.toArray(new String[pairs.size()]);
	}

	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			int H = Integer.parseInt(br.readLine());
			String[] board = new String[H];
			for (int i = 0; i < H; ++i) {
				board[i] = br.readLine();
			}

			SameColorPairs scp = new SameColorPairs();
			String[] ret = scp.removePairs(board);

			System.out.println(ret.length);
			for (int i = 0; i < ret.length; ++i) {
				System.out.println(ret[i]);
			}
			System.out.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

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 SAState {

	public static final boolean useTime = true;

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

	public double startTemperature = 18;
	public double endTemperature = 4;
	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;
		lastAcceptTemperature = startTemperature;
		startTime = useTime ? SameColorPairs.watch.getSecond() : numIterations;

		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 ? SameColorPairs.watch.getSecond() : numIterations;
	}

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

	public boolean accept(double newScore, double currentScore) {
		assert newScore - currentScore > 0;
		assert 1.0 / inverseTemperature >= 0;
		return SameColorPairs.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
	}

	public boolean acceptUsingTomerunsPruning(double newScore, double currentScore) {
		assert newScore - currentScore > 0;
		assert 1.0 / inverseTemperature >= 0;
		return (-newScore + currentScore) * (inverseTemperature) > -10 && SameColorPairs.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
	}

	public boolean acceptUsingTomerunsPruning(double deltaScore) {
		assert deltaScore < 0;
		assert 1.0 / inverseTemperature >= 0;
		return (deltaScore) * (inverseTemperature) > -10 && SameColorPairs.rng.nextDouble() < Math.exp((deltaScore) * (inverseTemperature));
	}

	public boolean acceptUsingTomerunsPruningAndEvb(double newScore, double currentScore) {
		assert newScore - currentScore > 0;
		assert 1.0 / inverseTemperature >= 0;
		return (-newScore + currentScore) * (inverseTemperature) > -10 && (SameColorPairs.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (-newScore + currentScore) * (inverseTemperature));
	}

	public boolean acceptUsingTomerunsPruningAndEvb(double deltaScore) {
		assert deltaScore < 0;
		assert 1.0 / inverseTemperature >= 0;
		return deltaScore * inverseTemperature > -10 && (SameColorPairs.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + deltaScore * inverseTemperature);
	}

}




Score 60秒で実行した時の例。結構ばらつきます。seed1 で40台が出ることもあれば44から改善しない時もあります。

  1. 40.815795138332106
  2. 43.53807408847798
  3. 124.3846766524884
  4. 24.75026428309017
  5. 44.13945193661654
  6. 99.17847374135275
  7. 20.081364429410037
  8. 70.93028342586867
  9. 80.47902244156333
  10. 191.91519882649064

1



Approach

ランダムに2点を交換するSA。
スコアは1番時間がかかる Vehicle の時間なので、交換する2点でスコアが変化しない時は、代わりに全 Vehicle の時間の合計を使う。
参考文献にあったストリングモデルのようなモデルを使う。

ストリングモデルは、次のような感じで
0, Vehicle1 の頂点集合, 0, Vehicle2 の頂点集合, ... , 0, VehicleM の頂点集合, 0
0で区切るモデルです。

私が使ったモデルは、次のような感じで
Vehicle2 の頂点集合の後半, Vehicle1 のID, Vehicle1 の頂点集合,  VehicleM のID, VehicleM の頂点集合, ... , Vehicle2 のID, Vehicle2 の頂点集合の前半
各VehicleのIDで区切って、リング状です。


Code

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

public class VehicleRoutingProblem {
static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();

private int numPoints;
private int numVehicles;
private int[] x;
private int[] y;
private int[] cap;
private double[] inverseSpeed;
private double[][] distancePointToPoint;
private double[] times;
private int[] nodeToPoint;
private int[] pointToNode;
private SAState sa = new SAState();
private double sumTimes;
private double maxTimes;

private int[] nodeToVehicle;

private String[] run(int n, int m, int depotX, int depotY, int[] x, int[] y, int[] cap, int[] speed) {
init(n, m, depotX, depotY, x, y, cap, speed);
solve();

double max = 0;
for (int v = 0; v < numVehicles; v++) {
double timeV = calculateTime2(v);
Utils.debug("v", v, "time", timeV);
max = Math.max(max, timeV);
}
Utils.debug("time", watch.getSecondString(), "score", max);

return makeResult();
}

private String[] makeResult() {
String[] res = new String[numVehicles];
for (int v = 0; v < numVehicles; v++) {

ArrayList<Integer> points = new ArrayList<>();
for (int node = (pointToNode[numPoints + v] + 1) % nodeToPoint.length;; node = next(node)) {
if (isStartNode(node)) {
break;
}
points.add(nodeToPoint[node]);
}

StringBuilder sb = new StringBuilder();
sb.append("" + points.size());
for (int i = 0; i < points.size(); i++) {
sb.append(" " + points.get(i));
}
res[v] = sb.toString();
}
return res;
}

private void solve() {
SA();
}

private double calculateTime2(int vehicle) {
double distance = 0;
int startNode = pointToNode[numPoints + vehicle];
for (int i = 0;; i++) {
int node = (startNode + i) % nodeToPoint.length;
int nextNode = next(node);
if (i > 0 && isStartNode(node)) {
break;
}
distance += calculatePartDistance(vehicle, node, nextNode);
}
return distance * inverseSpeed[vehicle];
}

private void SA() {
double second = Math.ceil(watch.getSecond());
int mask = (1 << 10) - 1;
sa.init();
for (;; sa.numIterations++) {
if ((sa.numIterations & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {

Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.countChange / sa.numIterations), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5f", maxTimes), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}

sa.updateTemperature();
sa.updateRange();

if (watch.getSecond() > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.countChange / sa.numIterations), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5f", maxTimes), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

change();
}
}

private void change() {
swap();
}

private int[] used;
private double[] currentTimes;

private int node1 = 0;

private void swap() {
node1++;
if (node1 >= nodeToPoint.length) {
node1 = 0;
}
int node2 = (int) ((nodeToPoint.length - 1) * rng.nextDouble());
if (node2 >= node1) {
node2++;
}
if (isStartNode(node1) || isStartNode(node2)) {
int originalVehicle1 = nodeToVehicle[node1];
int originalVehicle2 = nodeToVehicle[node2];

swap(node1, node2);

int vehicle1 = searchVehicle(node1);
int vehicle2 = searchVehicle(node2);

double newSum = sumTimes;
double newMax = 0;

for (int v = 0; v < numVehicles; v++) {
if (v == originalVehicle1 || v == originalVehicle2 || v == vehicle1 || v == vehicle2) {
currentTimes[v] = times[v];
times[v] = calculateTime2(v);
newSum += times[v] - currentTimes[v];
}
newMax = Math.max(newMax, times[v]);
}

double deltaScore = newMax - maxTimes;
if (Math.abs(deltaScore) < 1e-6) {
deltaScore = newSum - sumTimes;
}

sa.countChange++;
if (deltaScore < 1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) {
sa.countAccept++;
if (!(deltaScore < 1e-9)) {
sa.lastAcceptTemperature = sa.inverseTemperature;
}
sumTimes = newSum;
maxTimes = newMax;
for (int v = 0; v < numVehicles; v++) {
if (v == originalVehicle1 || v == originalVehicle2 || v == vehicle1 || v == vehicle2) {
setNodeToVehicle(v);
}
}

} else {
swap(node1, node2);
for (int v = 0; v < numVehicles; v++) {
if (v == originalVehicle1 || v == originalVehicle2 || v == vehicle1 || v == vehicle2) {
times[v] = currentTimes[v];
}
}
}
} else {
int vehicle1 = nodeToVehicle[node1];
int vehicle2 = nodeToVehicle[node2];
int previousNode1 = previous(node1);
int nextNode1 = next(node1);

int previousNode2 = previous(node2);
int nextNode2 = next(node2);

double currentTime1 = (calculatePartDistance(vehicle1, previousNode1, node1, previousNode1) + calculatePartDistance(vehicle1, node1, node1, nextNode1)) * inverseSpeed[vehicle1];
double currentTime2 = (calculatePartDistance(vehicle2, previousNode2, node2, previousNode2) + calculatePartDistance(vehicle2, node2, node2, nextNode2)) * inverseSpeed[vehicle2];

double newTime1;
double newTime2;
if (node1 == previousNode2) {
newTime1 = (calculatePartDistance(vehicle1, previousNode1, node2, previousNode1) + calculatePartDistance(vehicle1, node1, node2, node1)) * inverseSpeed[vehicle1];
newTime2 = (calculatePartDistance(vehicle2, previousNode2, node1, node2) + calculatePartDistance(vehicle2, node2, node1, nextNode2)) * inverseSpeed[vehicle2];
} else if (node2 == previousNode1) {
newTime1 = (calculatePartDistance(vehicle1, previousNode1, node2, node1) + calculatePartDistance(vehicle1, node1, node2, nextNode1)) * inverseSpeed[vehicle1];
newTime2 = (calculatePartDistance(vehicle2, previousNode2, node1, previousNode2) + calculatePartDistance(vehicle2, node2, node1, node2)) * inverseSpeed[vehicle2];
} else {
newTime1 = (calculatePartDistance(vehicle1, previousNode1, node2, previousNode1) + calculatePartDistance(vehicle1, node1, node2, nextNode1)) * inverseSpeed[vehicle1];
newTime2 = (calculatePartDistance(vehicle2, previousNode2, node1, previousNode2) + calculatePartDistance(vehicle2, node2, node1, nextNode2)) * inverseSpeed[vehicle2];
}
double newSum = sumTimes + newTime1 - currentTime1 + newTime2 - currentTime2;
double newMax = 0;
if (Math.abs(times[vehicle1] - maxTimes) < 1e-6 || Math.abs(times[vehicle2] - maxTimes) < 1e-6) {
times[vehicle1] += newTime1 - currentTime1;
times[vehicle2] += newTime2 - currentTime2;
for (int v = 0; v < numVehicles; v++) {
newMax = Math.max(newMax, times[v]);
}
} else {
times[vehicle1] += newTime1 - currentTime1;
times[vehicle2] += newTime2 - currentTime2;
newMax = Math.max(maxTimes, Math.max(times[vehicle1], times[vehicle2]));
}
double deltaScore = newMax - maxTimes;
if (Math.abs(deltaScore) < 1e-6) {
deltaScore = newSum - sumTimes;
}

sa.countChange++;
if (deltaScore < 1e-9 || sa.acceptUsingTomerunsPruning((deltaScore))) {
sa.countAccept++;
if (!(deltaScore < 1e-9)) {
sa.lastAcceptTemperature = sa.inverseTemperature;
}

swap(node1, node2);

sumTimes = newSum;
maxTimes = newMax;
} else {
times[vehicle1] -= newTime1 - currentTime1;
times[vehicle2] -= newTime2 - currentTime2;
}
}
}

private void setNodeToVehicle(int vehicle) {
nodeToVehicle[pointToNode[numPoints + vehicle]] = vehicle;
for (int node = next(pointToNode[numPoints + vehicle]);; node = next(node)) {
if (isStartNode(node)) {
break;
}
nodeToVehicle[node] = vehicle;
}
}

private void swap(int node1, int node2) {
int swap = nodeToPoint[node1];
nodeToPoint[node1] = nodeToPoint[node2];
nodeToPoint[node2] = swap;
pointToNode[nodeToPoint[node1]] = node1;
pointToNode[nodeToPoint[node2]] = node2;
}

private boolean isStartNode(int node) {
return nodeToPoint[node] >= numPoints;
}

private double calculatePartDistance(int vehicle, int node, int nodeFrom, int nodeTo) {
if (isEmpty(node, vehicle)) {
return distancePointToPoint[nodeToPoint[nodeFrom]][numPoints + vehicle] + distancePointToPoint[numPoints + vehicle][nodeToPoint[nodeTo]];
} else {
return distancePointToPoint[nodeToPoint[nodeFrom]][nodeToPoint[nodeTo]];
}
}

private double calculatePartDistance(int vehicle, int nodeFrom, int nodeTo) {
return calculatePartDistance(vehicle, nodeFrom, nodeFrom, nodeTo);
}

private boolean isEmpty(int node, int vehicle) {
int startNode = pointToNode[numPoints + vehicle];
int diffNodes = node >= startNode ? (node - startNode) : (node + pointToNode.length - startNode);
assert diffNodes >= 0 : Utils.toString("num", diffNodes);
return diffNodes % cap[vehicle] == 0;
}

private int searchVehicle(int node) {
if (isStartNode(node)) {
assert nodeToPoint[node] - numPoints >= 0 && nodeToPoint[node] - numPoints < numVehicles;
return nodeToPoint[node] - numPoints;
}
int vehicleNode = -1;
int maxVehicleNode = -1;
for (int v = 0; v < numVehicles; v++) {
if (pointToNode[numPoints + v] <= node) {
vehicleNode = Math.max(vehicleNode, pointToNode[numPoints + v]);
}
maxVehicleNode = Math.max(maxVehicleNode, pointToNode[numPoints + v]);
}
if (vehicleNode == -1) {
return nodeToPoint[maxVehicleNode] - numPoints;
}
return nodeToPoint[vehicleNode] - numPoints;
}

private int next(int node) {
return (node + 1) % nodeToPoint.length;
}

private int previous(int node) {
return (node - 1 + nodeToPoint.length) % nodeToPoint.length;
}

private void init(int n, int m, int depotX, int depotY, int[] x, int[] y, int[] cap, int[] speed) {
numPoints = n;
numVehicles = m;
this.x = new int[numPoints + numVehicles];
for (int i = 0; i < numPoints; i++) {
this.x[i] = x[i];
}
for (int i = 0; i < numVehicles; i++) {
this.x[numPoints + i] = depotX;
}
this.y = new int[numPoints + numVehicles];
for (int i = 0; i < numPoints; i++) {
this.y[i] = y[i];
}
for (int i = 0; i < numVehicles; i++) {
this.y[numPoints + i] = depotY;
}

this.cap = cap;
inverseSpeed = new double[speed.length];
for (int i = 0; i < speed.length; i++) {
inverseSpeed[i] = 1.0 / speed[i];
}

distancePointToPoint = new double[numPoints + numVehicles][numPoints + numVehicles];
for (int i = 0; i < numPoints + numVehicles; i++) {
for (int j = 0; j < numPoints + numVehicles; j++) {
double dx = this.x[i] - this.x[j];
double dy = this.y[i] - this.y[j];
distancePointToPoint[i][j] = Math.sqrt(dx * dx + dy * dy);
}
}

nodeToPoint = new int[numPoints + numVehicles];
for (int i = 0; i < numPoints + numVehicles; i++) {
nodeToPoint[i] = i;
}
pointToNode = new int[numPoints + numVehicles];
for (int i = 0; i < numPoints + numVehicles; i++) {
pointToNode[nodeToPoint[i]] = i;
}

times = new double[numVehicles];
for (int v = 0; v < numVehicles; v++) {
times[v] = calculateTime2(v);
}

sumTimes = 0;
maxTimes = 0;
for (int v = 0; v < numVehicles; v++) {
sumTimes += times[v];
maxTimes = Math.max(maxTimes, times[v]);
}
used = new int[numPoints + numVehicles];
Arrays.fill(used, -1);

currentTimes = new double[numVehicles];

nodeToVehicle = new int[numPoints + numVehicles];
for (int v = 0; v < numVehicles; v++) {
setNodeToVehicle(v);
}

Utils.debug("N", n, "M", m);

}

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

String[] split = reader.readLine().trim().split(" ");
int N = Integer.parseInt(split[0]);
int M = Integer.parseInt(split[1]);
split = reader.readLine().trim().split(" ");
int depotX = Integer.parseInt(split[0]);
int depotY = Integer.parseInt(split[1]);

int[] x = new int[N];
int[] y = new int[N];

for (int i = 0; i < N; i++) {
split = reader.readLine().trim().split(" ");
x[i] = Integer.parseInt(split[0]);
y[i] = Integer.parseInt(split[1]);
}

int[] cap = new int[M];
int[] speed = new int[M];

for (int i = 0; i < M; i++) {
split = reader.readLine().trim().split(" ");
cap[i] = Integer.parseInt(split[0]);
speed[i] = Integer.parseInt(split[1]);
}

VehicleRoutingProblem vrp = new VehicleRoutingProblem();
String[] ret = vrp.run(N, M, depotX, depotY, x, y, cap, speed);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

}

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 SAState {

public static final boolean useTime = true;

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

public double startTemperature = 0.1;
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 countChange;
public int countAccept;

public void init() {
numIterations = 0;
countChange = 0;
countAccept = 0;
lastAcceptTemperature = startTemperature;
startTime = useTime ? VehicleRoutingProblem.watch.getSecond() : numIterations;

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 ? VehicleRoutingProblem.watch.getSecond() : numIterations;
}

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return VehicleRoutingProblem.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
}

public boolean acceptUsingTomerunsPruning(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return (-newScore + currentScore) * (inverseTemperature) > -10 && VehicleRoutingProblem.rng.nextDouble() < Math.exp(-(newScore - currentScore) * (inverseTemperature));
}

public boolean acceptUsingTomerunsPruning(double deltaScore) {
assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;
return (-deltaScore) * (inverseTemperature) > -10 && VehicleRoutingProblem.rng.nextDouble() < Math.exp(-(deltaScore) * (inverseTemperature));
}

public boolean acceptUsingTomerunsPruningAndEvb(double newScore, double currentScore) {
assert newScore - currentScore > 0;
assert 1.0 / inverseTemperature >= 0;
return (-newScore + currentScore) * (inverseTemperature) > -10 && (VehicleRoutingProblem.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (-newScore + currentScore) * (inverseTemperature));
}

}

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

}

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

}



↑このページのトップヘ