Submission #2106523


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 bestScore = eval(ans);
		int[][] bestOutput = new int[1000][3];
		for (int i = 0; i < bestOutput.length; i++) {
			bestOutput[i] = Arrays.copyOf(ans[i], ans[i].length);
		}
		while (System.currentTimeMillis() < et) {
			int[][] tmpOutput = new int[1000][3];
			for (int i = 0; i < pnum; i++) {
				int x = rnd.nextInt(100);
				int y = rnd.nextInt(100);
				int h = rnd.nextInt(100) + 1;
				tmpOutput[i][0] = x;
				tmpOutput[i][1] = y;
				tmpOutput[i][2] = h;
			}
			int tmpScore = eval(tmpOutput);
			if(bestScore > tmpScore){
				bestOutput = tmpOutput;
				for (int i = 0; i < bestOutput.length; i++) {
					bestOutput[i] = Arrays.copyOf(tmpOutput[i], tmpOutput[i].length);
				}
			}
		}
		for (int i = 0; i < bestOutput.length; i++) {
			ans[i] = Arrays.copyOf(bestOutput[i], bestOutput[i].length);
		}
	}

	// 山の外周に沿って斜め移動
	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

Submission Time
Task A - 山型足し算
User tsukammo
Language Java8 (OpenJDK 1.8.0)
Score 9769240193
Code Size 3142 Byte
Status AC
Exec Time 5747 ms
Memory 49104 KB

Judge Result

Set Name Sample All
Score / Max Score 193177578 / 200000000 9576062615 / 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 5747 ms 45788 KB
subtask_01_01.txt AC 5725 ms 44652 KB
subtask_01_02.txt AC 5721 ms 43044 KB
subtask_01_03.txt AC 5737 ms 44284 KB
subtask_01_04.txt AC 5711 ms 46904 KB
subtask_01_05.txt AC 5724 ms 44008 KB
subtask_01_06.txt AC 5728 ms 46396 KB
subtask_01_07.txt AC 5725 ms 44676 KB
subtask_01_08.txt AC 5725 ms 43476 KB
subtask_01_09.txt AC 5729 ms 43596 KB
subtask_01_10.txt AC 5723 ms 43876 KB
subtask_01_11.txt AC 5735 ms 44516 KB
subtask_01_12.txt AC 5741 ms 46680 KB
subtask_01_13.txt AC 5735 ms 47972 KB
subtask_01_14.txt AC 5725 ms 44328 KB
subtask_01_15.txt AC 5735 ms 43792 KB
subtask_01_16.txt AC 5744 ms 42772 KB
subtask_01_17.txt AC 5727 ms 44204 KB
subtask_01_18.txt AC 5741 ms 45244 KB
subtask_01_19.txt AC 5732 ms 44292 KB
subtask_01_20.txt AC 5711 ms 45948 KB
subtask_01_21.txt AC 5726 ms 43580 KB
subtask_01_22.txt AC 5726 ms 45020 KB
subtask_01_23.txt AC 5715 ms 45724 KB
subtask_01_24.txt AC 5730 ms 44532 KB
subtask_01_25.txt AC 5727 ms 43968 KB
subtask_01_26.txt AC 5740 ms 43352 KB
subtask_01_27.txt AC 5729 ms 45644 KB
subtask_01_28.txt AC 5730 ms 43996 KB
subtask_01_29.txt AC 5732 ms 46916 KB
subtask_01_30.txt AC 5721 ms 47144 KB
subtask_01_31.txt AC 5716 ms 46244 KB
subtask_01_32.txt AC 5733 ms 46444 KB
subtask_01_33.txt AC 5735 ms 44912 KB
subtask_01_34.txt AC 5736 ms 44200 KB
subtask_01_35.txt AC 5739 ms 46080 KB
subtask_01_36.txt AC 5733 ms 44012 KB
subtask_01_37.txt AC 5728 ms 43724 KB
subtask_01_38.txt AC 5719 ms 43768 KB
subtask_01_39.txt AC 5728 ms 44644 KB
subtask_01_40.txt AC 5734 ms 45120 KB
subtask_01_41.txt AC 5730 ms 49104 KB
subtask_01_42.txt AC 5714 ms 45216 KB
subtask_01_43.txt AC 5729 ms 45056 KB
subtask_01_44.txt AC 5727 ms 47204 KB
subtask_01_45.txt AC 5735 ms 46860 KB
subtask_01_46.txt AC 5718 ms 45056 KB
subtask_01_47.txt AC 5735 ms 45212 KB
subtask_01_48.txt AC 5711 ms 45180 KB
subtask_01_49.txt AC 5722 ms 46328 KB