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