結果
| 問題 | No.5013 セクスタプル (open) |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2023-01-07 22:24:47 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,964 ms / 2,000 ms |
| コード長 | 17,993 bytes |
| コンパイル時間 | 2,427 ms |
| 実行使用メモリ | 58,488 KB |
| スコア | 18,572 |
| 最終ジャッジ日時 | 2023-01-07 22:28:12 |
| 合計ジャッジ時間 | 204,278 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
import java.util.Arrays;import java.util.Scanner;public class Main {private long[] coef = new long[] { 1L, 1L << 6, 1L << 12, 1L << 18, 1L << 24, 1L << 30, };private int[] dice_mask = new int[36];private long[] dice_count = new long[36];private int score = (int) -1e18;private int[][] table = new int[6][6];private int bestScore = (int) -1e18;private int[][] bestTable = new int[6][6];private SAState sa = new SAState();private int[] part_score_row = new int[6];private long[] counts_row = new long[6];private int[] part_score_column = new int[6];private long[] counts_column = new long[6];private int[][] remove_row = new int[6][6];private int[][] remove_column = new int[6][6];public static void main(String[] args) throws Exception {new Main().run();}private void run() {read();solve();write();}private void read() {try (final Scanner in = new Scanner(System.in)) {for (int i = 0; i < 36; i++) {for (int j = 0; j < 6; j++) {int dice = in.nextInt() - 1;dice_mask[i] |= (1 << dice);dice_count[i] += coef[dice];if (i == 0 && j == 0) {Constants.watch.init();}}}} catch (Exception e) {e.printStackTrace();}}private void solve() {greedy();multiSA();Utils.debug(bestScore, sa.numIterations);}private void greedy() {for (int r = 0; r < 6; r++) {for (int c = 0; c < 6; c++) {table[r][c] = r * 6 + c;counts_row[r] += dice_count[table[r][c]];counts_column[c] += dice_count[table[r][c]];}}update_remove();score = calculateScore();saveBest();}private void saveBest() {if (score > bestScore) {bestScore = score;for (int r = 0; r < 6; r++) {for (int c = 0; c < 6; c++) {bestTable[r][c] = table[r][c];}}}}private void restoreBest() {for (int i = 0; i < 6; i++) {counts_row[i] = 0;counts_column[i] = 0;}for (int r = 0; r < 6; r++) {for (int c = 0; c < 6; c++) {table[r][c] = bestTable[r][c];counts_row[r] += dice_count[table[r][c]];counts_column[c] += dice_count[table[r][c]];}}update_remove();score = calculateScore();}private void multiSA() {int numRestart = 100;double startTime = Constants.watch.getSecond();double endTime = 1.8;double remainTime = endTime - startTime;double startStartTemperature = 2;double endStartTemperature = 0.5;for (double restart = 0; restart < numRestart; restart++) {sa.startTime = startTime + remainTime * restart / numRestart;sa.endTime = startTime + remainTime * (restart + 1) / numRestart;sa.startTemperature = endStartTemperature + (startStartTemperature - endStartTemperature) * ((numRestart - restart) / numRestart);sa.endTemperature = 0.5;SA();restoreBest();}}private void SA() {sa.init();for (;; ++sa.numIterations) {if ((sa.numIterations & ((1 << 10) - 1)) == 0) {sa.update();if (sa.isTLE()) {break;}}mutate();}}private void mutate() {swap();}private void swap() {int v1 = sa.numIterations % 36;final int r1 = v1 / 6;final int c1 = v1 % 6;int v2 = Constants.RNG.nextInt(35);if (v2 >= v1) {v2++;}final int r2 = v2 / 6;final int c2 = v2 % 6;final int current1 = table[r1][c1];final int current2 = table[r2][c2];int before = 0;int after = 0;int after_r1 = 0;int after_r2 = 0;int after_c1 = 0;int after_c2 = 0;if (r2 != r1) {before += part_score_row[r1];before += part_score_row[r2];after_r1 = partScore(remove_row[r1][c1] & dice_mask[current2], counts_row[r1] - dice_count[current1] + dice_count[current2]);after_r2 = partScore(remove_row[r2][c2] & dice_mask[current1], counts_row[r2] - dice_count[current2] + dice_count[current1]);after += after_r1;after += after_r2;}if (c2 != c1) {before += part_score_column[c1];before += part_score_column[c2];after_c1 = partScore(remove_column[r1][c1] & dice_mask[current2], counts_column[c1] - dice_count[current1] + dice_count[current2]);after_c2 = partScore(remove_column[r2][c2] & dice_mask[current1], counts_column[c2] - dice_count[current2] + dice_count[current1]);after += after_c1;after += after_c2;}int deltaScore = after - before;if (sa.accept(deltaScore)) {score += deltaScore;table[r1][c1] = current2;table[r2][c2] = current1;if (r2 != r1) {part_score_row[r1] = after_r1;part_score_row[r2] = after_r2;counts_row[r1] -= dice_count[current1];counts_row[r2] -= dice_count[current2];counts_row[r1] += dice_count[current2];counts_row[r2] += dice_count[current1];}if (c2 != c1) {part_score_column[c1] = after_c1;part_score_column[c2] = after_c2;counts_column[c1] -= dice_count[current1];counts_column[c2] -= dice_count[current2];counts_column[c1] += dice_count[current2];counts_column[c2] += dice_count[current1];}update_remove(r1, c1, r2, c2);saveBest();} else {}}private void update_remove() {for (int r = 0; r < 6; r++) {for (int c = 0; c < 6; c++) {{int mask = -1;for (int r2 = 0; r2 < 6; r2++) {if (r2 == r) {continue;}mask &= dice_mask[table[r2][c]];}remove_column[r][c] = mask;}{int mask = -1;for (int c2 = 0; c2 < 6; c2++) {if (c2 == c) {continue;}mask &= dice_mask[table[r][c2]];}remove_row[r][c] = mask;}}}}private void update_remove(int r3, int c3, int r4, int c4) {{int r = r3;for (int c = 0; c < 6; c++) {{int mask = -1;for (int r2 = 0; r2 < 6; r2++) {if (r2 == r) {continue;}mask &= dice_mask[table[r2][c]];}remove_column[r][c] = mask;}{int mask = -1;for (int c2 = 0; c2 < 6; c2++) {if (c2 == c) {continue;}mask &= dice_mask[table[r][c2]];}remove_row[r][c] = mask;}}}{int r = r4;for (int c = 0; c < 6; c++) {{int mask = -1;for (int r2 = 0; r2 < 6; r2++) {if (r2 == r) {continue;}mask &= dice_mask[table[r2][c]];}remove_column[r][c] = mask;}{int mask = -1;for (int c2 = 0; c2 < 6; c2++) {if (c2 == c) {continue;}mask &= dice_mask[table[r][c2]];}remove_row[r][c] = mask;}}}{int c = c3;for (int r = 0; r < 6; r++) {{int mask = -1;for (int r2 = 0; r2 < 6; r2++) {if (r2 == r) {continue;}mask &= dice_mask[table[r2][c]];}remove_column[r][c] = mask;}{int mask = -1;for (int c2 = 0; c2 < 6; c2++) {if (c2 == c) {continue;}mask &= dice_mask[table[r][c2]];}remove_row[r][c] = mask;}}}{int c = c4;for (int r = 0; r < 6; r++) {{int mask = -1;for (int r2 = 0; r2 < 6; r2++) {if (r2 == r) {continue;}mask &= dice_mask[table[r2][c]];}remove_column[r][c] = mask;}{int mask = -1;for (int c2 = 0; c2 < 6; c2++) {if (c2 == c) {continue;}mask &= dice_mask[table[r][c2]];}remove_row[r][c] = mask;}}}}private int calculateScore() {int score = 0;for (int r = 0; r < 6; r++) {final int partScoreRow = partScoreRow(r);part_score_row[r] = partScoreRow;score += partScoreRow;}for (int c = 0; c < 6; c++) {final int partScoreColumn = partScoreColumn(c);part_score_column[c] = partScoreColumn;score += partScoreColumn;}return score;}private int partScoreRow(int r) {int mask = dice_mask[table[r][0]] & dice_mask[table[r][1]] & dice_mask[table[r][2]] & dice_mask[table[r][3]] & dice_mask[table[r][4]] &dice_mask[table[r][5]];final long v = counts_row[r];return partScore(mask, v);}private int partScoreColumn(int c) {int mask = dice_mask[table[0][c]] & dice_mask[table[1][c]] & dice_mask[table[2][c]] & dice_mask[table[3][c]] & dice_mask[table[4][c]] &dice_mask[table[5][c]];final long v = counts_column[c];return partScore(mask, v);}private int partScore(int mask, final long v) {return (int) (((mask & (1 << 0)) == 0 ? 0 : -3 + (v & 63)) + ((mask & (1 << 1)) == 0 ? 0 : -3 + ((v >>> 6) & 63)) + ((mask & (1 << 2)) == 0 ?0 : -3 + ((v >>> 12) & 63)) + ((mask & (1 << 3)) == 0 ? 0 : -3 + ((v >>> 18) & 63)) + ((mask & (1 << 4)) == 0 ? 0 : -3 + ((v >>> 24) & 63)) + ((mask & (1 << 5)) == 0 ? 0 : -3 + ((v >>> 30) & 63)));}private void write() {String[] s = new String[36];for (int i = 0; i < s.length; i++) {s[i] = "";}for (int r = 0; r < 6; r++) {for (int c = 0; c < 6; c++) {s[bestTable[r][c]] = (r + 1) + " " + (c + 1);}}StringBuilder sb = new StringBuilder();for (int i = 0; i < 36; i++) {sb.append(s[i]).append('\n');}System.out.print(sb.toString());System.out.flush();}}class SAState {public static final boolean useTime = true;public double startTime;public double endTime;public double time;public double startTemperature;public double endTemperature;public double inverseTemperature;public double lastAcceptTemperature;public double startRange;public double endRange;public double range;public int numIterations;public int validIterations;public int acceptIterations;private double[] log = new double[32768];public SAState() {for (int i = 0; i < log.length; i++) {log[i] = Math.log((i + 0.5) / log.length);}}public void init() {numIterations = 0;validIterations = 0;acceptIterations = 0;startTime = useTime ? Constants.watch.getSecond() : numIterations;update();lastAcceptTemperature = inverseTemperature;}public void update() {updateTime();updateTemperature();}public boolean useExp = !true;public void updateTemperature() {if (useExp) {double time0to1 = elapsedPercentage(startTime, endTime, time);double startY = startTemperature;double endY = endTemperature;double startX = Math.log(startY);double endX = Math.log(endY);double xStartToEnd = interpolate(startX, endX, time0to1);double temperature = Math.exp(xStartToEnd);inverseTemperature = 1.0 / temperature;} else {double time0to1 = elapsedPercentage(startTime, endTime, time);double startY = startTemperature;double endY = endTemperature;double temperature = interpolate(startY, endY, time0to1);inverseTemperature = 1.0 / temperature;}}private double elapsedPercentage(double min, double max, double v) {return (v - min) / (max - min);}private double interpolate(double v0, double v1, double d0to1) {return v0 + (v1 - v0) * d0to1;}public void updateRange() {range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);}public void updateTime() {time = useTime ? Constants.watch.getSecond() : numIterations;}public boolean isTLE() {return time >= endTime;}public boolean accept(double deltaScore) {return acceptB(deltaScore);}public boolean acceptB(double deltaScore) {validIterations++;if (deltaScore > -1e-9) {acceptIterations++;return true;}double d = deltaScore * inverseTemperature;if (d < -10) {return false;}if (log[Constants.RNG.nextInt() & 32767] < d) {acceptIterations++;lastAcceptTemperature = inverseTemperature;return true;}return false;}public boolean acceptS(double deltaScore) {validIterations++;if (deltaScore < 1e-9) {acceptIterations++;return true;}double d = -deltaScore * inverseTemperature;if (d < -10) {return false;}if (log[Constants.RNG.nextInt() & 32767] < d) {acceptIterations++;lastAcceptTemperature = inverseTemperature;return true;}return false;}}final class Utils {private Utils() {}public static final void debug(Object... o) {System.err.println(toString(o));System.err.flush();}public static final String toString(Object... o) {return Arrays.deepToString(o);}public static boolean isValid(int v, int min, int minUpper) {return v >= min && v < minUpper;}}class Watch {private long start;public Watch() {init();}public double getSecond() {return (System.nanoTime() - start) * 1e-9;}public void init() {init(System.nanoTime());}private void init(long start) {this.start = start;}public String getSecondString() {return toString(getSecond());}public static final String toString(double second) {if (second < 60) {return String.format("%5.2fs", second);} else if (second < 60 * 60) {int minute = (int) (second / 60);return String.format("%2dm%2ds", minute, (int) (second % 60));} else {int hour = (int) (second / (60 * 60));int minute = (int) (second / 60);return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));}}}interface Constants {Watch watch = new Watch();PCG_XSH_RR RNG = new PCG_XSH_RR(System.nanoTime());}final class PCG_XSH_RR {private long state = 5342;public PCG_XSH_RR(final long state) {this.state = state;}public int nextInt() {final long oldstate = state;state = oldstate * 6364136223846793005L + 521L;final int xorshift = (int) (((oldstate >>> 18) ^ oldstate) >>> 27);final int rotation = (int) (oldstate >>> 59);return (xorshift >>> rotation) | (xorshift << (-rotation & 31));}public int nextInt(int n) {return (int) (n * nextDouble());}public double nextDouble() {return (nextInt() >>> 1) * 4.6566128730773926E-10;}}