Submission #2199659
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); // update ここから long bestScore = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { bestScore += Math.pow(diff[i][j], 2); } } // update ここまで int loopCount = 0; long currentTime = System.currentTimeMillis(); double C = timeLimit * 100; // 許容する確率定数。適当に弄る。 double forceLine; // 許容ライン。時間経過によりラインを厳しくしていく。 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); // update ここから long tmpScore = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { tmpScore += Math.pow(diff[i][j], 2); } } // update ここまで currentTime = System.currentTimeMillis(); forceLine = (et - currentTime) / 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++) { 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 | 9997889498 |
Code Size | 6062 Byte |
Status | AC |
Exec Time | 5739 ms |
Memory | 37316 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 199959257 / 200000000 | 9797930241 / 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 | 5712 ms | 34284 KB |
subtask_01_01.txt | AC | 5715 ms | 36392 KB |
subtask_01_02.txt | AC | 5728 ms | 33328 KB |
subtask_01_03.txt | AC | 5726 ms | 34164 KB |
subtask_01_04.txt | AC | 5719 ms | 33936 KB |
subtask_01_05.txt | AC | 5729 ms | 35960 KB |
subtask_01_06.txt | AC | 5724 ms | 35580 KB |
subtask_01_07.txt | AC | 5708 ms | 37008 KB |
subtask_01_08.txt | AC | 5726 ms | 34064 KB |
subtask_01_09.txt | AC | 5729 ms | 34360 KB |
subtask_01_10.txt | AC | 5724 ms | 37156 KB |
subtask_01_11.txt | AC | 5727 ms | 36560 KB |
subtask_01_12.txt | AC | 5728 ms | 36744 KB |
subtask_01_13.txt | AC | 5728 ms | 32044 KB |
subtask_01_14.txt | AC | 5739 ms | 34584 KB |
subtask_01_15.txt | AC | 5720 ms | 35612 KB |
subtask_01_16.txt | AC | 5708 ms | 34972 KB |
subtask_01_17.txt | AC | 5728 ms | 33912 KB |
subtask_01_18.txt | AC | 5730 ms | 34580 KB |
subtask_01_19.txt | AC | 5707 ms | 35724 KB |
subtask_01_20.txt | AC | 5722 ms | 32444 KB |
subtask_01_21.txt | AC | 5708 ms | 33016 KB |
subtask_01_22.txt | AC | 5729 ms | 36152 KB |
subtask_01_23.txt | AC | 5719 ms | 37316 KB |
subtask_01_24.txt | AC | 5726 ms | 34572 KB |
subtask_01_25.txt | AC | 5725 ms | 36696 KB |
subtask_01_26.txt | AC | 5718 ms | 36364 KB |
subtask_01_27.txt | AC | 5721 ms | 37052 KB |
subtask_01_28.txt | AC | 5728 ms | 36724 KB |
subtask_01_29.txt | AC | 5717 ms | 36600 KB |
subtask_01_30.txt | AC | 5726 ms | 34628 KB |
subtask_01_31.txt | AC | 5724 ms | 36268 KB |
subtask_01_32.txt | AC | 5718 ms | 35028 KB |
subtask_01_33.txt | AC | 5729 ms | 35848 KB |
subtask_01_34.txt | AC | 5707 ms | 35912 KB |
subtask_01_35.txt | AC | 5709 ms | 36068 KB |
subtask_01_36.txt | AC | 5718 ms | 34656 KB |
subtask_01_37.txt | AC | 5729 ms | 34388 KB |
subtask_01_38.txt | AC | 5725 ms | 33908 KB |
subtask_01_39.txt | AC | 5726 ms | 33304 KB |
subtask_01_40.txt | AC | 5707 ms | 35004 KB |
subtask_01_41.txt | AC | 5707 ms | 34932 KB |
subtask_01_42.txt | AC | 5719 ms | 33816 KB |
subtask_01_43.txt | AC | 5716 ms | 34680 KB |
subtask_01_44.txt | AC | 5717 ms | 34988 KB |
subtask_01_45.txt | AC | 5725 ms | 36508 KB |
subtask_01_46.txt | AC | 5726 ms | 33208 KB |
subtask_01_47.txt | AC | 5732 ms | 35080 KB |
subtask_01_48.txt | AC | 5728 ms | 34244 KB |
subtask_01_49.txt | AC | 5722 ms | 35540 KB |