EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

https://community.topcoder.com/tc?module=SimpleStats&c=long_comp_history&d1=statistics&d2=longHistory&cr=23100980

からコピーしました。

たくさん参加できてよかった。
最後にレッドコーダーになって卒業したような感じになってる(笑)。

Screenshot_2019-07-28 TopcoderScreenshot_2019-07-28 Topcoder(1)




Marathon Match Competition History
Competition Rank Provisional Score Final Score Rating Volatility  
Marathon Match 109 5 974997.97 982722.26 2247 356 Results
Marathon Match 108 5 960841.58 962704.80 2184 360 Results
Marathon Match 107 3 999445.95 999660.28 2114 357 Results
Marathon Match 106 10 832400.00 827020.00 1996 286 Results
Marathon Match 104 17 642496.82 656202.92
Results
Marathon Match 103 24 942046.30 934844.01 1971 311 Results
Marathon Match 102 11 824271.58 832897.36 2057 270 Results
TCO MM 4 21 729465.17 729907.40 2093 283 Results
Lightning Round 12 957290.68 951042.19 2091 311 Results
2018 TCO Marathon Round 3 39 942684.66 939023.79 2027 305 Results
DS Challenge: Use IBM Watson to Predict Customer Reviews 21 401858.86 412368.92

Results
Marathon Match 101: World Cup MM 3 759117.65 765470.59 2046 332 Results
Round 2 16 859918.70 865640.24 1959 309 Results
Silverline Media Advertisement Placement Challenge ROUND 13 971645.13 971932.22 1881 290 Results
Round 1 61 996372.21 995505.51 1959 266 Results
Poland Lightning Round 30 812700.54 819858.22 1982 290 Results
Marathon Match 100 24 799733.10 780255.34 1966 319 Results
Problem Statement Classification 15 1.00 0.00

Results
Marathon Match 99 13 837313.57 858045.96 1921 338 Results
Marathon Match 98 20 817032.52 818347.56 1895 370 Results
Konica-Minolta: Detecting Abnormality for Automated QA 27 5219.23 12053.77

Results
Marathon Match 97 7 885000.00 900434.09 1907 410 Results
Intel Movidius 20 0.00 0.00

Results
Marathon Match 96 15 942728.84 938321.33 1818 406 Results
Auto Cracks 16 383329.60 214332.73

Results
RoadDetector 24 0.00 0.00

Results
AutoTops Marathon 15 780406.69 755409.75

Results
Urban Mapper 3D 13 279279.05 1.00

Results
Marathon Match 95 10 848333.33 853075.76 1859 440 Results
MudLogging OCR Optimization 19 86724.81 108562.89

Results
Functional Map of the World 57 13062.17 1306.22

Results
Poland Lightning Round 6 931011.24 933831.46 1876 486 Results
Fishing MM 2 28 906747.67 897292.68 1798 467 Results
Marathon Match 94 3 930447.76 957611.94 1765 474 Results
Morgoth's Crown 11 500000.00 50000.00

Results
Pathology Segmentation *TCO17* 44 693728.97 734890.01 1623 412 Results
Round 3 32 178087.19 223511.81 1708 413 Results
TCO Announcement Fun Round 21 402691.25 408390.45 1663 447 Results
Round 2 39 565436.89 561273.79 1789 402 Results
Round 1 16 784329.22 785288.38 1790 446 Results
Lung Cancer Round 2 *TCO17* 6 424319.25 471030.35

Results
Spacenet Round 2 *TCO17* 13 830.24 83.02

Results
Marathon Match 93 11 509329.14 519315.36 1697 446 Results
HMS Lung Cancer 20 6078.76 6078.76 1622 464 Results
Connectivity Map Round 2 24 0.00 0.00

Results
Marathon Match 92 7 603933.51 590899.12 1803 304 Results
MMRF 3 460837.23 339361.16

Results
SpaceNet Challenge 19 36156.57 36156.57 1748 313 Results
Price Predictor 12 952235.50 918926.95 1830 292 Results
Marathon Match 91 7 478585.04 438491.03 1883 301 Results
Bonus Round 6 165338.25 133538.58

Results
Round 2 17 171823.63 181077.71

Results
Master Challenge 7 0.00 0.00

Results
Fishing MM 26 902027.55 958040.40 1836 316 Results
How Much Can a Nation Save 10 977644.52 977658.11

Results
Email Mini MM 7 417879.51 418959.39 1901 317 Results
Mixed Effects Models 14 94.76 947560.87

Results
Time Series Learning 13 98.90 989070.27 1894 352 Results
Matrix Completion Models 10 88.09 880396.62

Results
Tree Based Models 14 98.90 989070.27

Results
Connectivity Map 24 1253523.43 1246389.78 1969 352 Results
Round 3 14 994776.32 993678.57 2048 339 Results
Round 2 11 912854.93 902926.79 2002 356 Results
DNAS 1 29 292357.43 282791.29 1922 351 Results
UKHO Tidal Streams F2F 6 100325.10 83052.74

Results
Round 1 45 814035.66 808172.07 1967 377 Results
Electronic Parts MM 12 997119.19 983209.70 2022 394 Results
Atrocity MM 8 2477.16 14229.02 2017 434 Results
Marathon Match 17 814037.14 809128.72 1996 481 Results
Computational Oncology 13 404059.74 387091.37

Results
Marathon Match 90 2 99.03 1976.98 2002 527 Results
Marathon Match 89 7 85.23 856.08 1843 462 Results
Marathon Match 88 9 702632.66 714598.08 1972 309 Results
Spoken Languages 2 26 729560.00 1874440.00 1774 490 Results
Marathon Match 87 2 972912.30 970273.56 1944 339 Results
Master Data Management 29 129836.27 130443.91 1814 235 Results
Quake Predictor 8 13352.84 6411.48 1903 168 Results
Round 3 48 285879.07 309510.63 1905 187 Results
Spoken Languages 19 483600.00 1175600.00

Results
Round 2 28 820828.40 817464.50 1938 194 Results
Round 1 13 90.41 1813.37 1932 216 Results
Optimal Sampling 20 889438.95 951311.65 1852 161 Results
Robot Vision Tracker Extended 9 262374.56 349543.72

Results
Robot Vision Tracker 9 539880.67 262303.81 1864 178 Results
Marathon Match 86 15 96.62 484.03 1851 197 Results
Child Stuntedness 5 20 159765.09 169243.59 1812 203 Results
Trip Safety 12 241857.18 275789.19 1826 225 Results
Antibody Marathon Match 18 22345.25 4088.21 1784 234 Results
Active Molecules 11 918761.13 919207.20 1850 217 Results
Child Stuntedness 4 10 729345.30 725957.49 1795 211 Results
Facial Emotions 10 196198.31 200780.42 1793 237 Results
Child Stuntedness 3 10 455024.09 420637.46 1797 266 Results
Design of Experiments 21 696820.14 595380.83 1742 274 Results
2014 TCO Marathon Round 3 14 918122.44 926193.03 1801 281 Results
2014 TCO Marathon Round 2 66 492090.94 497787.66 1687 200 Results
2014 TCO Marathon Round 1 62 650328.44 663720.94 1688 226 Results
AlleleClassifier 48 849291.68 823976.86 1639 234 Results
Marathon Match 82 21 893036.32 889156.97 1685 248 Results
Tech Challenge for Atrocity Prevention 22 131.96 196.48 1617 246 Results
2013 TCO Marathon Round 3 105 793967.96 803143.94 1587 276 Results
2013 TCO Marathon Round 2 78 77.54 1559.03 1592 319 Results
2013 TCO Marathon Round 1 26 895274.84 890448.44 1593 372 Results
Marathon Match 78 60 599543.77 583386.36 1412 280 Results
ISS Longeron Challenge 82 152794.37 154272.49 1474 321 Results
HMS Challenge #4 19 17893.11 17252.96 1384 385 Results



Approach 2点を交換する焼きなまし法です。

  • 脳死SA : 98以上
  • 直前の Line の位置から左右8以内の位置に制限する + 10%の確率でその左右8以内の位置で最もスコアが良くなる位置と交換 : 99以上(試行回数が3分の1になってしまったので多分ですけど。)



source code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class LineUp {
private int R;
private int C;
private int[] heights;
private IntSet[] rToPerformerIndexes;
private int[][] bestRxcToPerformerIndex;
private int[][] idealHeights;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();

private double score;
private double bestScore;

private long SSEHeight = 0;
private long SAEDist = 0;
private long bestSSEHeight = 0;
private long bestSAEDist = 0;

public int[] getLineup(int[] heights, int[] arrangements) {
init(heights, arrangements);
solve();
return makeSolution();
}

private void init(int[] heights, int[] arrangements) {
C = heights.length;
this.heights = heights;
R = arrangements.length / C;
idealHeights = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
idealHeights[r][c] = arrangements[r * C + c];
}
}
rToPerformerIndexes = new IntSet[R];
for (int r = 0; r < R; r++) {
rToPerformerIndexes[r] = new IntSet(C);
for (int c = 0; c < C; c++) {
rToPerformerIndexes[r].add(c);
}
}

score = calculateScore();

bestRxcToPerformerIndex = new int[R][C];
bestScore = 1e9;
saveBest();
}

private void solve() {
double numRestart = 1;
double startTemperature = 3;
double endTemperature = 0;
double startTime = watch.getSecond();
double endTime = 9.5;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA();
loadBest();
}
}

private void SA() {
double second = Math.ceil(watch.getSecond());
sa.init();
for (;; sa.numIterations++) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
loadBest();
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%7.5f", score), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), String.format("%.6f", sa.startTemperature), String.format("%.6f", sa.endTemperature));
break;
}
if (watch.getSecond() > second) {
second++;
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%7.5f", score), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), String.format("%.6f", sa.startTemperature), String.format("%.6f", sa.endTemperature));
}
}

mutate();
}
Utils.debug("SA", "time", watch.getSecondString());
}

private void mutate() {
double random = 1.1 * rng.nextDouble();
if (random < 1) {
swapNear();
} else {
swapNearBest();
}
}

private void swap() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = 0;
deltaSSEHeight -= SEHeight(r, c, pi);
deltaSSEHeight -= SEHeight(r, c2, pi2);
deltaSSEHeight += SEHeight(r, c, pi2);
deltaSSEHeight += SEHeight(r, c2, pi);

long deltaSAEDist = 0;
deltaSAEDist -= AEDist(r, c, pi);
deltaSAEDist -= AEDist(r, c2, pi2);
deltaSAEDist += AEDist(r, c, pi2);
deltaSAEDist += AEDist(r, c2, pi);

double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
saveBest();
} else {
}
}

private void swapNear() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int pi = getPerformerIndex(r, c);
int prevC = getC(r - 1, pi);
int dc = 8;
int cl = Math.max(0, prevC - dc);
int cr = Math.min(prevC + dc, C - 1);
int c2 = (int) sa.interpolate(cl, cr + 1, rng.nextDouble());
if (c2 == c) {
return;
}

int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = -SEHeight(r, c, pi) - SEHeight(r, c2, pi2) + SEHeight(r, c, pi2) + SEHeight(r, c2, pi);
long deltaSAEDist = -AEDist(r, c, pi) - AEDist(r, c2, pi2) + AEDist(r, c, pi2) + AEDist(r, c2, pi);
double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
saveBest();
}
}

private void swapNearBest() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int pi = getPerformerIndex(r, c);
int prevC = getC(r - 1, pi);
int dc = 8;
int cl = Math.max(0, prevC - dc);
int cr = Math.min(prevC + dc, C - 1);
double bestdeltaScore = 1e99;
long bestSSE = 0;
long bestSAE = 0;
int bestc2 = -1;
for (int c2 = cl; c2 <= cr; c2++) {
if (c2 == c) {
continue;
}

int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = -SEHeight(r, c, pi) - SEHeight(r, c2, pi2) + SEHeight(r, c, pi2) + SEHeight(r, c2, pi);
long deltaSAEDist = -AEDist(r, c, pi) - AEDist(r, c2, pi2) + AEDist(r, c, pi2) + AEDist(r, c2, pi);
double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (deltaScore2 < bestdeltaScore) {
bestdeltaScore = deltaScore2;
bestSSE = deltaSSEHeight;
bestSAE = deltaSAEDist;
bestc2 = c2;
}
}
if (sa.accept(bestdeltaScore)) {
swap(r, c, bestc2);
SSEHeight += bestSSE;
SAEDist += bestSAE;
score += bestdeltaScore;
saveBest();
}
}

private void swapCandidate2() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}
int c3 = c;
while (c3 == c || c3 == c2) {
c3 = (int) (C * rng.nextDouble());
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
int pi3 = getPerformerIndex(r, c3);

long deltaSSEHeight2 = 0;
deltaSSEHeight2 -= SEHeight(r, c, pi);
deltaSSEHeight2 -= SEHeight(r, c2, pi2);
deltaSSEHeight2 += SEHeight(r, c, pi2);
deltaSSEHeight2 += SEHeight(r, c2, pi);

long deltaSAEDist2 = 0;
deltaSAEDist2 -= AEDist(r, c, pi);
deltaSAEDist2 -= AEDist(r, c2, pi2);
deltaSAEDist2 += AEDist(r, c, pi2);
deltaSAEDist2 += AEDist(r, c2, pi);

long deltaSSEHeight3 = 0;
deltaSSEHeight3 -= SEHeight(r, c, pi);
deltaSSEHeight3 -= SEHeight(r, c3, pi3);
deltaSSEHeight3 += SEHeight(r, c, pi3);
deltaSSEHeight3 += SEHeight(r, c3, pi);

long deltaSAEDist3 = 0;
deltaSAEDist3 -= AEDist(r, c, pi);
deltaSAEDist3 -= AEDist(r, c3, pi3);
deltaSAEDist3 += AEDist(r, c, pi3);
deltaSAEDist3 += AEDist(r, c3, pi);

double newScore2 = SAEDist + deltaSAEDist2 + Math.sqrt(SSEHeight + deltaSSEHeight2);
double deltaScore2 = newScore2 - score;

double newScore3 = SAEDist + deltaSAEDist3 + Math.sqrt(SSEHeight + deltaSSEHeight3);
double deltaScore3 = newScore3 - score;

if (deltaScore2 < deltaScore3) {
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight2;
SAEDist += deltaSAEDist2;
score += deltaScore2;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore3)) {
swap(r, c, c3);
SSEHeight += deltaSSEHeight3;
SAEDist += deltaSAEDist3;
score += deltaScore3;
saveBest();
} else {
}
}

}

private void swapCandidate3() {
int r = (int) (R * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2;
while ((c2 = (int) (C * rng.nextDouble())) == c) {
}
int c3 = c;
while (c3 == c || c3 == c2) {
c3 = (int) (C * rng.nextDouble());
}
int c4 = c;
while (c4 == c || c4 == c2 || c4 == c3) {
c4 = (int) (C * rng.nextDouble());
}

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
int pi3 = getPerformerIndex(r, c3);
int pi4 = getPerformerIndex(r, c4);

long deltaSSEHeight2 = 0;
deltaSSEHeight2 -= SEHeight(r, c, pi);
deltaSSEHeight2 -= SEHeight(r, c2, pi2);
deltaSSEHeight2 += SEHeight(r, c, pi2);
deltaSSEHeight2 += SEHeight(r, c2, pi);

long deltaSAEDist2 = 0;
deltaSAEDist2 -= AEDist(r, c, pi);
deltaSAEDist2 -= AEDist(r, c2, pi2);
deltaSAEDist2 += AEDist(r, c, pi2);
deltaSAEDist2 += AEDist(r, c2, pi);

long deltaSSEHeight3 = 0;
deltaSSEHeight3 -= SEHeight(r, c, pi);
deltaSSEHeight3 -= SEHeight(r, c3, pi3);
deltaSSEHeight3 += SEHeight(r, c, pi3);
deltaSSEHeight3 += SEHeight(r, c3, pi);

long deltaSAEDist3 = 0;
deltaSAEDist3 -= AEDist(r, c, pi);
deltaSAEDist3 -= AEDist(r, c3, pi3);
deltaSAEDist3 += AEDist(r, c, pi3);
deltaSAEDist3 += AEDist(r, c3, pi);

long deltaSSEHeight4 = 0;
deltaSSEHeight4 -= SEHeight(r, c, pi);
deltaSSEHeight4 -= SEHeight(r, c4, pi4);
deltaSSEHeight4 += SEHeight(r, c, pi4);
deltaSSEHeight4 += SEHeight(r, c4, pi);

long deltaSAEDist4 = 0;
deltaSAEDist4 -= AEDist(r, c, pi);
deltaSAEDist4 -= AEDist(r, c4, pi4);
deltaSAEDist4 += AEDist(r, c, pi4);
deltaSAEDist4 += AEDist(r, c4, pi);

double newScore2 = SAEDist + deltaSAEDist2 + Math.sqrt(SSEHeight + deltaSSEHeight2);
double deltaScore2 = newScore2 - score;

double newScore3 = SAEDist + deltaSAEDist3 + Math.sqrt(SSEHeight + deltaSSEHeight3);
double deltaScore3 = newScore3 - score;

double newScore4 = SAEDist + deltaSAEDist4 + Math.sqrt(SSEHeight + deltaSSEHeight4);
double deltaScore4 = newScore4 - score;

if (deltaScore2 < deltaScore3) {
if (deltaScore2 < deltaScore4) {
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight2;
SAEDist += deltaSAEDist2;
score += deltaScore2;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore4)) {
swap(r, c, c4);
SSEHeight += deltaSSEHeight4;
SAEDist += deltaSAEDist4;
score += deltaScore4;
saveBest();
} else {
}
}
} else {
if (deltaScore3 < deltaScore4) {
if (sa.accept(deltaScore3)) {
swap(r, c, c3);
SSEHeight += deltaSSEHeight3;
SAEDist += deltaSAEDist3;
score += deltaScore3;
saveBest();
} else {
}
} else {
if (sa.accept(deltaScore4)) {
swap(r, c, c4);
SSEHeight += deltaSSEHeight4;
SAEDist += deltaSAEDist4;
score += deltaScore4;
saveBest();
} else {
}
}
}

}

private void saveBest() {
if (score < bestScore) {
bestScore = score;
bestSSEHeight = SSEHeight;
bestSAEDist = SAEDist;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
bestRxcToPerformerIndex[r][c] = rToPerformerIndexes[r].get(c);
}
}
}
}

private void loadBest() {
score = bestScore;
SSEHeight = bestSSEHeight;
SAEDist = bestSAEDist;
for (int r = 0; r < R; r++) {
rToPerformerIndexes[r].clear();
for (int c = 0; c < C; c++) {
rToPerformerIndexes[r].add(bestRxcToPerformerIndex[r][c]);
}
}
}

private void prevPos() {
int r = 1 + (int) ((R - 1) * rng.nextDouble());
int c = (int) (C * rng.nextDouble());
int c2 = getC(r - 1, getPerformerIndex(r, c));

int pi = getPerformerIndex(r, c);
int pi2 = getPerformerIndex(r, c2);
long deltaSSEHeight = 0;
deltaSSEHeight -= SEHeight(r, c, pi);
deltaSSEHeight -= SEHeight(r, c2, pi2);
deltaSSEHeight += SEHeight(r, c, pi2);
deltaSSEHeight += SEHeight(r, c2, pi);

long deltaSAEDist = 0;
deltaSAEDist -= AEDist(r, c, pi);
deltaSAEDist -= AEDist(r, c2, pi2);
deltaSAEDist += AEDist(r, c, pi2);
deltaSAEDist += AEDist(r, c2, pi);

double newScore2 = SAEDist + deltaSAEDist + Math.sqrt(SSEHeight + deltaSSEHeight);
double deltaScore2 = newScore2 - score;
if (sa.accept(deltaScore2)) {
swap(r, c, c2);
SSEHeight += deltaSSEHeight;
SAEDist += deltaSAEDist;
score += deltaScore2;
} else {
}
}

private double calculateScore() {
SAEDist = 0;
SSEHeight = 0;

for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
int pi = getPerformerIndex(r, c);
SSEHeight += SEHeight(r, c, pi);
SAEDist += AEDistPrev(r, c, pi);
}
}
return SAEDist + Math.sqrt(SSEHeight);
}

private long AEDist(int r, int c, int pi) {
return AEDistNext(r, c, pi) + AEDistPrev(r, c, pi);
}

private int AEDistPrev(int r, int c, int pi) {
int prevC = getC(r - 1, pi);
return Math.abs(prevC - c);
}

private int AEDistNext(int r, int c, int pi) {
if (r + 1 >= R) {
return 0;
}
int nextC = getC(r + 1, pi);
return Math.abs(nextC - c);
}

private int getPerformerIndex(int r, int c) {
return rToPerformerIndexes[r].get(c);
}

private int getC(int r, int performerIndex) {
if (r == -1) {
return performerIndex;
}
if (r >= R) {
throw new AssertionError();
}
return rToPerformerIndexes[r].indexOf(performerIndex);
}

private long SEHeight(int r, int c, int pi) {
long err = diffHeight(r, c, pi);
return err * err;
}

private long diffHeight(int r, int c, int performerIndex) {
return heights[performerIndex] - idealHeights[r][c];
}

private void swap(int r, int c, int c2) {
rToPerformerIndexes[r].swap(c, c2);
}

private int[] makeSolution() {
int[] ret = new int[R * C];
for (int r = 0, i = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
ret[i++] = getPerformerIndex(r, c);
}
}
return ret;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
int[] heights = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < heights.length; ++i) {
heights[i] = Integer.parseInt(br.readLine());
}
int[] arrangements = new int[Integer.parseInt(br.readLine())];
for (int i = 0; i < arrangements.length; ++i) {
arrangements[i] = Integer.parseInt(br.readLine());
}
LineUp sol = new LineUp();
int[] ret = sol.getLineup(heights, arrangements);
System.out.println(ret.length);
for (int i = 0; i < ret.length; i++) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (IOException e) {
e.printStackTrace();
}
}

}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 9.5;
public double time = startTime;

public double startTemperature = 40;
public double endTemperature = 1e9;
public double expTemperature = 1;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 101;
public double endRange = 3;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;
public int lastAcceptIterations;

private double minAbsDeltaScore;
private double maxAbsDeltaScore;
private MeanHelper helper = new MeanHelper();

private static final double[] log = new double[32768];
static {
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;

minAbsDeltaScore = 1e99;
maxAbsDeltaScore = 1e-99;
helper.clear();

startTime = useTime ? LineUp.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateStartTemperature() {
boolean useMean = true;
boolean useMax = !true;
if (useMean) {
double d = helper.mean(maxAbsDeltaScore);
d = d > 0 ? d : maxAbsDeltaScore;
startTemperature = (-1.0 * d) / Math.log(0.01);
} else if (useMax) {
startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(0.01);
} else {
startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(0.99);
}
}

public void updateEndTemperature() {
endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(0.00001);
}

public void updateTemperature() {
boolean useExp = !true;
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;
}
}

public void updateRange() {
}

public void updateTime() {
time = useTime ? LineUp.watch.getSecond() : numIterations;
}

private double elapsedPercentage(double min, double max, double v) {
return (v - min) / (max - min);
}

double interpolate(double v0, double v1, double d0to1) {
return v0 + (v1 - v0) * d0to1;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
double abs = Math.abs(deltaScore);
if (abs > 1e-9) {
helper.add(deltaScore);
minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
}
return acceptS(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;
if (deltaScore > -1e-9) {
acceptIterations++;
lastAcceptIterations = numIterations;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}
if (log[LineUp.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
lastAcceptIterations = numIterations;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;
if (deltaScore < 1e-9) {
acceptIterations++;
lastAcceptIterations = numIterations;
return true;
}
if (-deltaScore * inverseTemperature < -10) {
return false;
}
if (log[LineUp.rng.nextInt() & 32767] < -deltaScore * inverseTemperature) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
lastAcceptIterations = numIterations;
return true;
}
return false;
}

}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

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));
}
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class MeanHelper {
private double max;
private double min;
private double sum;
private double sumSquared;
private double sumCubed;
private double sumFourth;
private int count;

public MeanHelper() {
clear();
}

public void add(double value) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value;
double valueSquared = value * value;
sumSquared += valueSquared;
sumCubed += valueSquared * value;
sumFourth += valueSquared * valueSquared;
count++;
}

public void add(double value, double number) {
max = Math.max(max, value);
min = Math.min(min, value);
sum += value * number;
double valueSquared = value * value;
sumSquared += valueSquared * number;
sumCubed += valueSquared * value * number;
sumFourth += valueSquared * valueSquared * number;
count += number;
}

public double kurtosis(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
}

public double skewness(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double sigma = standardDeviation(0);
if (sigma == 0) {
return 0;
}
double mu = mean(0);
return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
}

public double mean() {
if (isEmpty()) {
throw new AssertionError();
}
return sum / count;
}

public double mean(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sum / count;
}

public double sumOfSquaredError() {
if (isEmpty()) {
throw new AssertionError();
}
return sumSquared - sum * sum / count;
}

public double sumOfSquaredError(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return sumSquared - sum * sum / count;
}

public double variance() {
if (isEmpty()) {
throw new AssertionError();
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double variance(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
double E_XX = sumSquared / count;
double E_X = sum / count;
return E_XX - E_X * E_X;
}

public double unbiasedVariance() {
if (count - 1 == 0) {
throw new AssertionError();
}
return (count * variance()) / (count - 1);
}

private double unbiasedVariance(double defaultValue) {
if (count - 1 == 0) {
return defaultValue;
}
return (count * variance()) / (count - 1);
}

public double standardDeviation() {
return Math.sqrt(variance());
}

public double standardDeviation(double defaultValue) {
return Math.sqrt(variance(defaultValue));
}

public double unbiasedStandardDeviation() {
return Math.sqrt(unbiasedVariance());
}

public double unbiasedStandardDeviation(double defaultValue) {
return Math.sqrt(unbiasedVariance(defaultValue));
}

public boolean isEmpty() {
return count == 0;
}

public void clear() {
max = Double.NEGATIVE_INFINITY;
min = Double.POSITIVE_INFINITY;
sum = 0;
sumSquared = 0;
sumCubed = 0;
sumFourth = 0;
count = 0;
}

public double max() {
if (isEmpty()) {
throw new AssertionError();
}
return max;
}

public double max(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return max;
}

public double min() {
if (isEmpty()) {
throw new AssertionError();
}
return min;
}

public double min(double defaultValue) {
if (isEmpty()) {
return defaultValue;
}
return min;
}

public int count() {
return count;
}

public double sum() {
return sum;
}

public double sumSquared() {
return sumSquared;
}
}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
swap(index, size - 1);
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public void swap(int index, int index2) {
assert index < size;
assert index2 < size;

int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[index2]] = index2;

}

public void swapValue(int index, int index2) {
assert index < size;
assert index2 < size;

int swap = valueToIndex[index];
valueToIndex[index] = valueToIndex[index2];
valueToIndex[index2] = swap;

indexToValue[valueToIndex[index]] = index;
indexToValue[valueToIndex[index2]] = index2;

}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

@Override
public String toString() {
return Arrays.toString(Arrays.copyOf(indexToValue, size()));
}
}


問題

Approach 焼きなまし法にしたけど、山登り法になりました。

  • 近傍1 : ガラスを消す
  • 近傍2 : ガラスを同一直線上に移動する
  • 近傍3 : ガラスを同一直線上でもっとも重複しているところに移動する
  • 近傍(使わなかった) : ガラスをランダムに置く
    • これをやった方が良いときもあったが、平均するとない方が良かった。


感想 IP ができるようなったかも。MM107 のようにほとんど最適解が求まるかと思ったけどそうでもなかった。

IP は koyumeishi さんの https://gist.github.com/koyumeishi/1dc332012cf875f7892844ddf17a5274 を参考にしました。



source code(Solver IP)





source code(Solver SA)





source code(Tester)


このページのトップヘ