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