Submission #2201789


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);
		long bestScore = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				bestScore += Math.pow(diff[i][j], 2);
			}
		}

		int loopCount = 0;

		long restTime = et - System.currentTimeMillis();
		double C = timeLimit * 100; // 許容する確率定数。適当に弄る。
		double forceLine; // 許容ライン。時間経過によりラインを厳しくしていく。
		int x, y, h;
		while (restTime > 0) {
			loopCount++;
			int[] tmpOutput = new int[3];
			int[] beforeOutput = new int[3];
			int n = rnd.nextInt(1000);
			long limitHigh = 10 + 110 * (restTime) / timeLimit;
			while (bestOutput[n][2] > limitHigh) {
				n = rnd.nextInt(1000);
			}
			beforeOutput[0] = bestOutput[n][0];
			beforeOutput[1] = bestOutput[n][1];
			beforeOutput[2] = bestOutput[n][2];

			x = Math.min(99, Math.max(0, beforeOutput[0] + rnd.nextInt(3) - 1));
			y = Math.min(99, Math.max(0, beforeOutput[1] + rnd.nextInt(3) - 1));
			h = Math.min(100, Math.max(1, beforeOutput[2] + rnd.nextInt(3) - 1));
			tmpOutput[0] = x;
			tmpOutput[1] = y;
			tmpOutput[2] = h;

			updateDiff(diff, beforeOutput, tmpOutput);
			long tmpScore = 0;
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					tmpScore += Math.pow(diff[i][j], 2);
				}
			}
			restTime = et - System.currentTimeMillis();
			forceLine = restTime / C;
			if (bestScore > tmpScore || forceLine > rnd.nextDouble()) {
				bestScore = tmpScore;
				bestOutput[n] = tmpOutput;
			} else {
				// rollback
				updateDiff(diff, tmpOutput, beforeOutput);
			}
		}
		bestScore = 0;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				bestScore += Math.abs(diff[i][j]);
			}
		}
		System.err.println("loop:" + loopCount + " " + bestScore);
		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++) {
			if (ans[i][2] > 0) {
				System.out.println(ans[i][0] + " " + ans[i][1] + " " + ans[i][2]);
			}
		}
	}
}

Submission Info

Submission Time
Task A - 山型足し算
User tsukammo
Language Java8 (OpenJDK 1.8.0)
Score 9998129683
Code Size 6115 Byte
Status AC
Exec Time 5731 ms
Memory 39500 KB

Judge Result

Set Name Sample All
Score / Max Score 199961571 / 200000000 9798168112 / 9800000000
Status
AC × 1
AC × 49
Set Name Test Cases
Sample example_01.txt
All subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt, subtask_01_35.txt, subtask_01_36.txt, subtask_01_37.txt, subtask_01_38.txt, subtask_01_39.txt, subtask_01_40.txt, subtask_01_41.txt, subtask_01_42.txt, subtask_01_43.txt, subtask_01_44.txt, subtask_01_45.txt, subtask_01_46.txt, subtask_01_47.txt, subtask_01_48.txt, subtask_01_49.txt
Case Name Status Exec Time Memory
example_01.txt AC 5708 ms 38896 KB
subtask_01_01.txt AC 5706 ms 38796 KB
subtask_01_02.txt AC 5709 ms 37140 KB
subtask_01_03.txt AC 5722 ms 37200 KB
subtask_01_04.txt AC 5713 ms 36252 KB
subtask_01_05.txt AC 5714 ms 35232 KB
subtask_01_06.txt AC 5724 ms 37668 KB
subtask_01_07.txt AC 5720 ms 37772 KB
subtask_01_08.txt AC 5712 ms 36404 KB
subtask_01_09.txt AC 5714 ms 37612 KB
subtask_01_10.txt AC 5731 ms 36584 KB
subtask_01_11.txt AC 5711 ms 35948 KB
subtask_01_12.txt AC 5725 ms 36364 KB
subtask_01_13.txt AC 5714 ms 37556 KB
subtask_01_14.txt AC 5725 ms 35668 KB
subtask_01_15.txt AC 5712 ms 38924 KB
subtask_01_16.txt AC 5701 ms 38108 KB
subtask_01_17.txt AC 5703 ms 37920 KB
subtask_01_18.txt AC 5722 ms 38204 KB
subtask_01_19.txt AC 5714 ms 37808 KB
subtask_01_20.txt AC 5725 ms 37668 KB
subtask_01_21.txt AC 5713 ms 38440 KB
subtask_01_22.txt AC 5711 ms 39500 KB
subtask_01_23.txt AC 5721 ms 35764 KB
subtask_01_24.txt AC 5714 ms 38240 KB
subtask_01_25.txt AC 5714 ms 37292 KB
subtask_01_26.txt AC 5717 ms 34688 KB
subtask_01_27.txt AC 5712 ms 38096 KB
subtask_01_28.txt AC 5714 ms 36524 KB
subtask_01_29.txt AC 5714 ms 38064 KB
subtask_01_30.txt AC 5711 ms 35824 KB
subtask_01_31.txt AC 5706 ms 37300 KB
subtask_01_32.txt AC 5702 ms 38936 KB
subtask_01_33.txt AC 5712 ms 36368 KB
subtask_01_34.txt AC 5723 ms 37296 KB
subtask_01_35.txt AC 5717 ms 39492 KB
subtask_01_36.txt AC 5714 ms 35932 KB
subtask_01_37.txt AC 5722 ms 38768 KB
subtask_01_38.txt AC 5713 ms 35540 KB
subtask_01_39.txt AC 5705 ms 37044 KB
subtask_01_40.txt AC 5722 ms 37680 KB
subtask_01_41.txt AC 5725 ms 34688 KB
subtask_01_42.txt AC 5721 ms 38636 KB
subtask_01_43.txt AC 5717 ms 38160 KB
subtask_01_44.txt AC 5711 ms 38328 KB
subtask_01_45.txt AC 5712 ms 37584 KB
subtask_01_46.txt AC 5702 ms 38012 KB
subtask_01_47.txt AC 5717 ms 36956 KB
subtask_01_48.txt AC 5708 ms 35420 KB
subtask_01_49.txt AC 5719 ms 37620 KB