Submission #2199385
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; // update ここから long currentTime = System.currentTimeMillis(); double C = timeLimit * 100; // 許容する確率定数。適当に弄る。 double forceLine; // 許容ライン。時間経過によりラインを厳しくしていく。 // update ここまで while (currentTime < 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 = Math.min(99, Math.max(0, beforeOutput[0] + rnd.nextInt(3) - 1)); int y = Math.min(99, Math.max(0, beforeOutput[1] + rnd.nextInt(3) - 1)); int 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); int tmpScore = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { tmpScore += Math.abs(diff[i][j]); } } // update ここから currentTime = System.currentTimeMillis(); forceLine = (et - currentTime) / C; if (bestScore > tmpScore || forceLine > rnd.nextDouble()) { // update ここまで bestScore = tmpScore; bestOutput[n] = tmpOutput; } else { // rollback updateDiff(diff, tmpOutput, beforeOutput); } } 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++) { 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 | 9997766553 |
Code Size | 5917 Byte |
Status | AC |
Exec Time | 5730 ms |
Memory | 38828 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 199952501 / 200000000 | 9797814052 / 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 | 5725 ms | 34420 KB |
subtask_01_01.txt | AC | 5713 ms | 36952 KB |
subtask_01_02.txt | AC | 5718 ms | 36872 KB |
subtask_01_03.txt | AC | 5717 ms | 33744 KB |
subtask_01_04.txt | AC | 5724 ms | 36900 KB |
subtask_01_05.txt | AC | 5709 ms | 33324 KB |
subtask_01_06.txt | AC | 5718 ms | 37060 KB |
subtask_01_07.txt | AC | 5703 ms | 33832 KB |
subtask_01_08.txt | AC | 5726 ms | 34828 KB |
subtask_01_09.txt | AC | 5723 ms | 34708 KB |
subtask_01_10.txt | AC | 5724 ms | 38032 KB |
subtask_01_11.txt | AC | 5710 ms | 33712 KB |
subtask_01_12.txt | AC | 5706 ms | 35292 KB |
subtask_01_13.txt | AC | 5728 ms | 34996 KB |
subtask_01_14.txt | AC | 5717 ms | 32972 KB |
subtask_01_15.txt | AC | 5722 ms | 36816 KB |
subtask_01_16.txt | AC | 5722 ms | 36636 KB |
subtask_01_17.txt | AC | 5713 ms | 34468 KB |
subtask_01_18.txt | AC | 5722 ms | 36776 KB |
subtask_01_19.txt | AC | 5723 ms | 36320 KB |
subtask_01_20.txt | AC | 5711 ms | 36868 KB |
subtask_01_21.txt | AC | 5718 ms | 35332 KB |
subtask_01_22.txt | AC | 5714 ms | 32404 KB |
subtask_01_23.txt | AC | 5716 ms | 36328 KB |
subtask_01_24.txt | AC | 5721 ms | 34704 KB |
subtask_01_25.txt | AC | 5725 ms | 38828 KB |
subtask_01_26.txt | AC | 5701 ms | 34996 KB |
subtask_01_27.txt | AC | 5730 ms | 36516 KB |
subtask_01_28.txt | AC | 5726 ms | 36288 KB |
subtask_01_29.txt | AC | 5725 ms | 35012 KB |
subtask_01_30.txt | AC | 5702 ms | 35736 KB |
subtask_01_31.txt | AC | 5714 ms | 36972 KB |
subtask_01_32.txt | AC | 5719 ms | 35796 KB |
subtask_01_33.txt | AC | 5713 ms | 36604 KB |
subtask_01_34.txt | AC | 5728 ms | 38664 KB |
subtask_01_35.txt | AC | 5708 ms | 36624 KB |
subtask_01_36.txt | AC | 5712 ms | 34256 KB |
subtask_01_37.txt | AC | 5703 ms | 34064 KB |
subtask_01_38.txt | AC | 5715 ms | 36524 KB |
subtask_01_39.txt | AC | 5724 ms | 33676 KB |
subtask_01_40.txt | AC | 5725 ms | 36800 KB |
subtask_01_41.txt | AC | 5719 ms | 35608 KB |
subtask_01_42.txt | AC | 5718 ms | 35112 KB |
subtask_01_43.txt | AC | 5724 ms | 34640 KB |
subtask_01_44.txt | AC | 5721 ms | 34500 KB |
subtask_01_45.txt | AC | 5707 ms | 33192 KB |
subtask_01_46.txt | AC | 5715 ms | 34276 KB |
subtask_01_47.txt | AC | 5711 ms | 34040 KB |
subtask_01_48.txt | AC | 5724 ms | 36112 KB |
subtask_01_49.txt | AC | 5724 ms | 34348 KB |