Submission #2106800

---

Source Code Expand

import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * Hack To The Future 2018
 *
 * @author tsukammo
 */
public class Main {

	Scanner sc = new Scanner(System.in);

	public static void main(String[] args) throws IOException {
		new Main().solve();
	}

	// 制約
	final static int N = 100, row = 100, col = 100, pnum = 1000;

	void solve() {
		input();
		init();
		simulate(); // new
		output();
	}

	Random rnd = new Random(20180217);
	int[][] ans = new int[1000][3];

	void init() {
		for (int i = 0; i < pnum; i++) {
			int x = rnd.nextInt(100);
			int y = rnd.nextInt(100);
			int h = rnd.nextInt(100) + 1;
			ans[i][0] = x;
			ans[i][1] = y;
			ans[i][2] = h;
		}
	}

	static final long timeLimit = 5500;

	void simulate() {
		long st = System.currentTimeMillis();
		long et = st + timeLimit;

		int[][] bestOutput = new int[1000][3];

		for (int i = 0; i < bestOutput.length; i++) {
			bestOutput[i] = Arrays.copyOf(ans[i], ans[i].length);
		}

		int[][] diff = makeDiff(bestOutput);
		int bestScore = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				bestScore += Math.abs(diff[i][j]);
			}
		}

		int loopCount = 0;
		while (System.currentTimeMillis() < et) {
			loopCount++;
			int[] tmpOutput = new int[3];
			int[] beforeOutput = new int[3];
			int n = rnd.nextInt(1000);
			beforeOutput[0] = bestOutput[n][0];
			beforeOutput[1] = bestOutput[n][1];
			beforeOutput[2] = bestOutput[n][2];

			int x = rnd.nextInt(100);
			int y = rnd.nextInt(100);
			int h = rnd.nextInt(100) + 1;
			tmpOutput[0] = x;
			tmpOutput[1] = y;
			tmpOutput[2] = h;

			updateDiff(diff, beforeOutput, tmpOutput);
			int tmpScore = 0;
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					tmpScore += Math.abs(diff[i][j]);
				}
			}

			if (bestScore > tmpScore) {
				bestScore = tmpScore;
				bestOutput[n] = tmpOutput;
			} else {
				// rollback
				updateDiff(diff, tmpOutput, beforeOutput);
			}
		}
		System.err.println("loop:" + loopCount);
		for (int i = 0; i < bestOutput.length; i++) {
			ans[i] = Arrays.copyOf(bestOutput[i], bestOutput[i].length);
		}
	}

	// 差分更新
	void updateDiff(int[][] diff, int[] before, int[] after) {

		// subtract
		int x = before[0];
		int y = before[1];
		int h = before[2];
		diff[x][y] += h;
		for (int plus = 1; plus < h; plus++) {
			int d = h - plus;
			x = before[0];
			y = before[1] - d;
			for (int j = 0; j < dx.length; j++) {
				for (int k = 0; k < d; k++) {
					x = x + dx[j];
					y = y + dy[j];
					if (outMap(x, y)) {
						continue;
					}
					diff[x][y] += plus;
				}
			}
		}

		// add
		x = after[0];
		y = after[1];
		h = after[2];
		diff[x][y] -= h;
		for (int plus = 1; plus < h; plus++) {
			int d = h - plus;
			x = after[0];
			y = after[1] - d;
			for (int j = 0; j < dx.length; j++) {
				for (int k = 0; k < d; k++) {
					x = x + dx[j];
					y = y + dy[j];
					if (outMap(x, y)) {
						continue;
					}
					diff[x][y] -= plus;
				}
			}
		}
	}

	int[][] makeDiff(int[][] output) {
		int[][] ret = new int[row][col];
		int[][] ansMap = new int[row][col];

		for (int i = 0; i < output.length; i++) {
			int x = output[i][0];
			int y = output[i][1];
			int h = output[i][2];
			ansMap[x][y] += h;
			for (int plus = 1; plus < h; plus++) {
				int d = h - plus;
				x = output[i][0];
				y = output[i][1] - d;
				for (int j = 0; j < dx.length; j++) {
					for (int k = 0; k < d; k++) {
						x = x + dx[j];
						y = y + dy[j];
						if (outMap(x, y)) {
							continue;
						}
						ansMap[x][y] += plus;
					}
				}
			}
		}

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				ret[i][j] = map[i][j] - ansMap[i][j];
			}
		}
		return ret;
	}

	// 山の外周に沿って斜め移動
	final static int dx[] = new int[] { 1, -1, -1, 1 };
	final static int dy[] = new int[] { 1, 1, -1, -1 };

	// シミュレータ
	int eval(int[][] output) {
		int ret = 0;
		int[][] ansMap = new int[row][col];

		for (int i = 0; i < output.length; i++) {
			int x = output[i][0];
			int y = output[i][1];
			int h = output[i][2];
			ansMap[x][y] += h;
			for (int plus = 1; plus < h; plus++) {
				int d = h - plus;
				x = output[i][0];
				y = output[i][1] - d;
				for (int j = 0; j < dx.length; j++) {
					for (int k = 0; k < d; k++) {
						x = x + dx[j];
						y = y + dy[j];
						if (outMap(x, y)) {
							continue;
						}
						ansMap[x][y] += plus;
					}
				}
			}
		}

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				ret += Math.abs(map[i][j] - ansMap[i][j]);
			}
		}
		return ret;
	}

	boolean outMap(int x, int y) {
		return !(x > -1 && y > -1 && x < row && y < col);
	}

	int[][] map = new int[row][col];

	void input() {
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				map[j][i] = sc.nextInt();
			}
		}
	}

	void output() {
		// 乱択した山を出力する
		System.out.println(ans.length);
		for (int i = 0; i < ans.length; i++) {
			System.out.println(ans[i][0] + " " + ans[i][1] + " " + ans[i][2]);
		}
	}
}

Submission Info

Judge Result