EvbCFfp1XB

problem and my answer.



学習器 Random Forest で Building の中か外かを推定。

特徴 半径{ 0, 3, 7, 11, }の中の、
RGBのR,G,B,gray , HSLのH,S,L  , gradient の magnitude , theta, wleiteさんのedge の、
平均、分散、skewness、kurtosis




Approach SAしました。


初期解は、下の図のように、斜めの直線が交差する形に配置しただけ。
Screenshot from 2017-12-13 00-49-24

近傍

初期解の形を維持するようにした。
  1. 2つの領域を交換する。
  2. 領域の長さを変える。短(長)くしたら、直線上の隣が長(短)くなる。
  3. 1つの領域を取り除いて(直線上の隣の領域にして)、別の領域を2つに分けて、どちらかに移る。

試行回数は1千万~5千万回。


source code

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

public class Main {
private static final int[] dr8 = new int[] { 0, -1, -1, -1, 0, 1, 1, 1, };
private static final int[] dc8 = new int[] { -1, -1, 0, 1, 1, 1, 0, -1, };

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

private static final int EMPTY = (1 << 10) - 1;

private int NV;
private int S0;
private int S;

private IntArray[] connectedVs;
private IntArray[] connectedVsEmb;

private boolean[][] isConnected;
private int[][] isConnectedEmb;
private int[][] inverseEmb;

private int score;
private int bestScore = (int) -1e9;
private int scoreBase = 5000;
private int scoreAdd = 0;
private int scoreBonus = 0;
private int scoreLoss = 0;

private int sumScores() {
return scoreBase + scoreAdd + scoreBonus - scoreLoss;
}

private IntArray[] embVSets;
private int preservedEdges;
private int NE;

private String[] run(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
init(NV, NE, u, v, NEmbV, NEmbE, a, b);
solve();
String[] solution = makeSolution();
return solution;
}

private void init(int NV, int NE, int[] u, int[] v, int NEmbV, int NEmbE, int[] a, int[] b) {
this.NV = NV;
this.NE = NE;

for (int i = 0; i < u.length; i++) {
u[i]--;
}
for (int i = 0; i < v.length; i++) {
v[i]--;
}

preservedEdges = 0;
this.isConnected = new boolean[NV][NV];
for (int i = 0; i < u.length; i++) {
isConnected[u[i]][v[i]] = true;
isConnected[v[i]][u[i]] = true;
}

connectedVs = new IntArray[NV];
for (int i = 0; i < connectedVs.length; i++) {
connectedVs[i] = new IntArray(1 << 9);
}
for (int i = 0; i < u.length; i++) {
connectedVs[u[i]].add(v[i]);
connectedVs[v[i]].add(u[i]);
}
this.isConnectedEmb = new int[NV][NV];
for (int i = 0; i < NV; i++) {
Arrays.fill(isConnectedEmb[i], -1);
}
connectedVsEmb = new IntArray[NV];
for (int i = 0; i < connectedVsEmb.length; i++) {
connectedVsEmb[i] = new IntArray(1 << 9);
}
for (int i = 0; i < a.length; i++) {
a[i]--;
}
for (int i = 0; i < b.length; i++) {
b[i]--;
}

S0 = (int) Math.sqrt(NEmbV + 1e-9);
S = S0;
if (S >= NV) {
S = NV;
}
embVSets = new IntArray[NV];
for (int i = 0; i < embVSets.length; i++) {
embVSets[i] = new IntArray(1 << 9);
}
bestEmbVSets = new IntArray[NV];
for (int i = 0; i < bestEmbVSets.length; i++) {
bestEmbVSets[i] = new IntArray(1 << 9);
}

inverseEmb = new int[S][S];
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
inverseEmb[r][c] = EMPTY;
}
}

scoreLoss -= NV;
}

private void solve() {

greedy();

score = scoreAdd;
saveBest();
SA();
}

private void greedy() {

int v = 0;
int usedPoints = 0;
for (int r = 0; r < S; r++) {

if (v >= NV) {
break;
}

int length = (S * S - usedPoints) / (NV - v);

for (int c = 0; c < S; c++) {
if (inverseEmb[r][c] != EMPTY) {
continue;
}

int r2 = r;
int c2 = c;
for (int l = 0; l < length; l++) {
if (inverseEmb[r2][c2] != EMPTY) {
break;
}

if (v >= NV) {
int r3;
int c3;
if (isLowerRightDirection(r2, c2)) {
r3 = r2 - dr8[5];
c3 = c2 - dc8[5];
} else {
r3 = r2 - dr8[7];
c3 = c2 - dc8[7];
}
if (!isValid(r3, 0, S)) {
break;
}
if (!isValid(c3, 0, S)) {
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
}
add(toEmbV(r2, c2), inverseEmb[r3][c3]);
} else {
add(toEmbV(r2, c2), v);
}
usedPoints++;

if (isLowerRightDirection(r2, c2)) {
r2 += dr8[5];
c2 += dc8[5];
} else {
r2 += dr8[7];
c2 += dc8[7];
}

if (!isValid(r2, 0, S)) {
break;
} else if (!isValid(c2, 0, S)) {
if (c2 < 0) {
c2 = 0;
} else if (c2 >= S) {
c2 = S - 1;
}
}
}

v++;
}
}

}

private boolean isLowerRightDirection(int r2, int c2) {
return (r2 + c2) % 2 == 0;
}

private boolean add(int embV, int v) {
int embR = toEmbR(embV);
int embC = toEmbC(embV);
assert inverseEmb[embR][embC] == EMPTY;
assert checkCanAdd(v, embR, embC);

inverseEmb[embR][embC] = v;
embVSets[v].add(embV);
scoreLoss++;
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[nextV][v]) {
continue;
}
if (isConnectedEmb[nextV][v] >= 0) {
continue;
}

isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
connectedVsEmb[v].add(nextV);

isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
connectedVsEmb[nextV].add(v);
scoreAdd += 100;
preservedEdges++;
if (preservedEdges == NE) {
scoreBonus += 100000;
}

}
return true;
}

private boolean adds(int[] embVs, int start, int end, int v) {
for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
assert inverseEmb[embR][embC] == EMPTY;
inverseEmb[embR][embC] = v;
embVSets[v].add(embV);
scoreLoss++;
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[v][nextV]) {
continue;
}
if (isConnectedEmb[v][nextV] >= 0) {
continue;
}
isConnectedEmb[v][nextV] = connectedVsEmb[v].length;
connectedVsEmb[v].add(nextV);
isConnectedEmb[nextV][v] = connectedVsEmb[nextV].length;
connectedVsEmb[nextV].add(v);
scoreAdd += 100;
preservedEdges++;
if (preservedEdges == NE) {
scoreBonus += 100000;
}
}
}
return true;
}

private IntArray change = new IntArray();

private int simulateAdds(int[] embVs, int start, int end, int v) {
countUsed++;

update(embVs, start, end, v);

int score = 0;

for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
assert nextV >= 0 && nextV < NV;
if (!isConnected[nextV][v]) {
continue;
}

if (used[nextV] == countUsed) {
continue;
}
used[nextV] = countUsed;
score += 100;
}
}
return score;

}

private void update(int[] embVs, int start, int end, int v) {
for (int i = start; i < end; i++) {
int embV = embVs[i];
int embR = toEmbR(embV);
int embC = toEmbC(embV);
change.add((embR << 20) | (embC << 10) | (inverseEmb[embR][embC]));
inverseEmb[embR][embC] = v;
}
}

private boolean checkCanAdd(int v, int embR, int embC) {
boolean b = embVSets[v].length == 0;
boolean b2 = false;
if (!b) {
for (int d = 0; d < dr8.length; d++) {
int embNextR = embR + dr8[d];
int embNextC = embC + dc8[d];
if (!isValid(embNextR, 0, S)) {
continue;
}
if (!isValid(embNextC, 0, S)) {
continue;
}
if (inverseEmb[embNextR][embNextC] == EMPTY) {
continue;
}
int nextV = inverseEmb[embNextR][embNextC];
if (nextV == v) {
b2 = true;
break;
}
}
}
boolean b3 = b || b2;
return b3;
}

private boolean removeAll(int v) {

for (int i = 0; i < embVSets[v].length; i++) {
int embV = embVSets[v].values[i];

int embR = toEmbR(embV);
int embC = toEmbC(embV);
inverseEmb[embR][embC] = EMPTY;

}
scoreLoss -= embVSets[v].length;
embVSets[v].clear();

for (int i = connectedVsEmb[v].length - 1; i >= 0; i--) {
int nextV = connectedVsEmb[v].values[i];
remove(v, nextV);
remove(nextV, v);
scoreAdd -= 100;
preservedEdges--;
if (preservedEdges + 1 == NE) {
scoreBonus -= 100000;
}
}
return true;

}

private void remove(int v, int nextV) {
int index = isConnectedEmb[v][nextV];
IntArray vs = connectedVsEmb[v];
if (index != vs.length - 1) {
int otherV = vs.values[vs.length - 1];
vs.values[vs.length - 1] = vs.values[index];
vs.values[index] = otherV;
isConnectedEmb[v][otherV] = index;
}
vs.remove();
isConnectedEmb[v][nextV] = -1;
}

private int[] used = new int[1 << 9];
private int countUsed = 0;
private SAState sa = new SAState();

private void SA() {
int mask = (1 << 10) - 1;

sa.init();
for (;; sa.loop++) {
if ((sa.loop & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {
loadBest();
break;
}

sa.updateTemperature();
}

change();
}
}

private void change() {
int random = (int) (3 * rng.nextDouble());
if (random == 0) {
swap();
} else if (random == 1) {
changeLength();
} else {
moveLine();
}
}

private IntArray embVs1 = new IntArray();
private IntArray embVs2 = new IntArray();
private IntArray embVs3 = new IntArray();

private void moveLine() {
int v = (int) (NV * rng.nextDouble());

boolean isUpper = rng.nextDouble() < 0.5;

int embV0;
{
assert checkOrder(v);
IntArray embVSet = embVSets[v];
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
int embR0 = toEmbR(embV0);
if (embR0 == 0) {
isUpper = false;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
} else if (embR0 == S - 1) {
isUpper = true;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
}
}

int sameLineV = EMPTY;
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);
if (isLowerRightDirection(embR0, embC0)) {
if (isUpper) {
int r1 = embR0 + dr8[1];
int c1 = embC0 + dc8[1];
if (c1 < 0) {
c1 = 0;
} else if (c1 >= S) {
c1 = S - 1;
}
if (isValid(r1, 0, S)) {
assert inverseEmb[r1][c1] != v;
assert inverseEmb[r1][c1] != EMPTY;
sameLineV = inverseEmb[r1][c1];
}
} else {
int r5 = embR0 + dr8[5];
int c5 = embC0 + dc8[5];
if (c5 < 0) {
c5 = 0;
} else if (c5 >= S) {
c5 = S - 1;
}
if (isValid(r5, 0, S)) {
assert inverseEmb[r5][c5] != v;
assert inverseEmb[r5][c5] != EMPTY;
sameLineV = inverseEmb[r5][c5];
}
}
} else {
if (isUpper) {
int r3 = embR0 + dr8[3];
int c3 = embC0 + dc8[3];
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
if (isValid(r3, 0, S)) {
assert inverseEmb[r3][c3] != v;
assert inverseEmb[r3][c3] != EMPTY;
sameLineV = inverseEmb[r3][c3];
}
} else {
int r7 = embR0 + dr8[7];
int c7 = embC0 + dc8[7];
if (c7 < 0) {
c7 = 0;
} else if (c7 >= S) {
c7 = S - 1;
}
if (isValid(r7, 0, S)) {
assert inverseEmb[r7][c7] != v;
assert inverseEmb[r7][c7] != EMPTY;
sameLineV = inverseEmb[r7][c7];
}
}
}

if (sameLineV == EMPTY) {
return;
}

int toV = (int) (NV * rng.nextDouble());
for (int k = 0; k < NV; k++) {
if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
toV = (int) (NV * rng.nextDouble());
} else {
break;
}
}
if (toV == v || toV == sameLineV || embVSets[toV].length <= 1) {
return;
}

int currentLengthToV = embVSets[toV].length;
boolean vIsUpperAtToV = rng.nextDouble() < 0.5;

if (isUpper) {
embVs1.clear();
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
} else {
embVs1.clear();
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
}
embVs3.clear();
for (int i = 0; i < embVSets[toV].length; i++) {
embVs3.add(embVSets[toV].values[i]);
}

int newLengthV = 1 + (int) ((currentLengthToV - 1) * rng.nextDouble());
int newLengthToV = currentLengthToV - newLengthV;
assert newLengthV > 0;
assert newLengthToV > 0;

int beforeV = -100 * connectedVsEmb[v].length;
int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
if (isConnectedEmb[sameLineV][v] >= 0) {
beforeSameLineV += 100;
}
int beforeToV = -100 * connectedVsEmb[toV].length;
if (isConnectedEmb[toV][v] >= 0) {
beforeToV += 100;
}
if (isConnectedEmb[toV][sameLineV] >= 0) {
beforeToV += 100;
}

if (vIsUpperAtToV) {
update(embVs3.values, 0, newLengthV, EMPTY);
update(embVs3.values, newLengthV, newLengthV + newLengthToV, EMPTY);
} else {
update(embVs3.values, 0, newLengthToV, EMPTY);
update(embVs3.values, newLengthToV, newLengthToV + newLengthV, EMPTY);
}

int afterSameLineV = simulateAdds(embVs1.values, 0, embVs1.length, sameLineV);
int afterV;
int afterToV;
if (vIsUpperAtToV) {
afterV = simulateAdds(embVs3.values, 0, newLengthV, v);
afterToV = simulateAdds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
} else {
afterToV = simulateAdds(embVs3.values, 0, newLengthToV, toV);
afterV = simulateAdds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
}

int newScore = score + beforeV + beforeToV + beforeSameLineV + afterV + afterToV + afterSameLineV;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(sameLineV);
removeAll(toV);

adds(embVs1.values, 0, embVs1.length, sameLineV);
if (vIsUpperAtToV) {
adds(embVs3.values, 0, newLengthV, v);
adds(embVs3.values, newLengthV, newLengthV + newLengthToV, toV);
} else {
adds(embVs3.values, 0, newLengthToV, toV);
adds(embVs3.values, newLengthToV, newLengthToV + newLengthV, v);
}

score = newScore;

saveBest();
}

}

private void changeLength() {
int v = (int) (NV * rng.nextDouble());

boolean isUpper = rng.nextDouble() < 0.5;

int embV0;
{
assert checkOrder(v);
IntArray embVSet = embVSets[v];
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
int embR0 = toEmbR(embV0);
if (embR0 == 0) {
isUpper = false;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
} else if (embR0 == S - 1) {
isUpper = true;
embV0 = embVSet.values[isUpper ? 0 : embVSet.length - 1];
}
}

int sameLineV = EMPTY;
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);
if (isLowerRightDirection(embR0, embC0)) {
if (isUpper) {
int r1 = embR0 + dr8[1];
int c1 = embC0 + dc8[1];
if (c1 < 0) {
c1 = 0;
} else if (c1 >= S) {
c1 = S - 1;
}
if (isValid(r1, 0, S)) {
assert inverseEmb[r1][c1] != v;
assert inverseEmb[r1][c1] != EMPTY;
sameLineV = inverseEmb[r1][c1];
}
} else {
int r5 = embR0 + dr8[5];
int c5 = embC0 + dc8[5];
if (c5 < 0) {
c5 = 0;
} else if (c5 >= S) {
c5 = S - 1;
}
if (isValid(r5, 0, S)) {
assert inverseEmb[r5][c5] != v;
assert inverseEmb[r5][c5] != EMPTY;
sameLineV = inverseEmb[r5][c5];
}
}
} else {
if (isUpper) {
int r3 = embR0 + dr8[3];
int c3 = embC0 + dc8[3];
if (c3 < 0) {
c3 = 0;
} else if (c3 >= S) {
c3 = S - 1;
}
if (isValid(r3, 0, S)) {
assert inverseEmb[r3][c3] != v;
assert inverseEmb[r3][c3] != EMPTY;
sameLineV = inverseEmb[r3][c3];
}
} else {
int r7 = embR0 + dr8[7];
int c7 = embC0 + dc8[7];
if (c7 < 0) {
c7 = 0;
} else if (c7 >= S) {
c7 = S - 1;
}
if (isValid(r7, 0, S)) {
assert inverseEmb[r7][c7] != v;
assert inverseEmb[r7][c7] != EMPTY;
sameLineV = inverseEmb[r7][c7];
}
}
}

if (sameLineV == EMPTY) {
return;
}

embVs1.clear();
if (isUpper) {
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
} else {
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
for (int i = 0; i < embVSets[sameLineV].length; i++) {
embVs1.add(embVSets[sameLineV].values[i]);
}
}

int currentLengthV = embVSets[v].length;
int currentLengthV2 = embVSets[sameLineV].length;

int beforeV = -100 * connectedVsEmb[v].length;
int beforeSameLineV = -100 * connectedVsEmb[sameLineV].length;
if (isConnectedEmb[sameLineV][v] >= 0) {
beforeSameLineV += 100;
}

int newLengthV = 1 + (int) ((currentLengthV + currentLengthV2 - 1) * rng.nextDouble());
int newLengthV2 = currentLengthV + currentLengthV2 - newLengthV;
assert newLengthV > 0;
assert newLengthV2 > 0;

int afterV;
int afterSameLineV;
if (isUpper) {
update(embVs1.values, newLengthV2, newLengthV + newLengthV2, EMPTY);
afterSameLineV = simulateAdds(embVs1.values, 0, newLengthV2, sameLineV);
afterV = simulateAdds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
} else {
update(embVs1.values, newLengthV, newLengthV + newLengthV2, EMPTY);
afterV = simulateAdds(embVs1.values, 0, newLengthV, v);
afterSameLineV = simulateAdds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
}

int newScore = score + beforeV + beforeSameLineV + afterV + afterSameLineV;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(sameLineV);

if (isUpper) {
adds(embVs1.values, 0, newLengthV2, sameLineV);
adds(embVs1.values, newLengthV2, newLengthV + newLengthV2, v);
} else {
adds(embVs1.values, 0, newLengthV, v);
adds(embVs1.values, newLengthV, newLengthV + newLengthV2, sameLineV);
}

score = newScore;
saveBest();
}
}

private boolean checkOrder(int v) {
IntArray embVSet = embVSets[v];
for (int i = 1; i < embVSet.length; i++) {
if (toEmbR(embVSet.values[i - 1]) >= toEmbR(embVSet.values[i])) {
return false;
}
}
return true;
}

private void swap() {
int v0 = (int) (NV * rng.nextDouble());
int embV0 = embVSets[v0].values[(int) (embVSets[v0].length * rng.nextDouble())];
int embR0 = toEmbR(embV0);
int embC0 = toEmbC(embV0);

int embNextR = -1;
int embNextC = -1;
while (!isValid(embNextR, 0, S) || !isValid(embNextC, 0, S) || inverseEmb[embNextR][embNextC] == v0) {
int d = (int) (dr8.length * rng.nextDouble());
embNextR = embR0 + dr8[d];
embNextC = embC0 + dc8[d];
}

int v = inverseEmb[embNextR][embNextC];

int v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
for (int k = 0; k < 3; k++) {
if (v2 != v) {
break;
}
v2 = connectedVs[v0].values[(int) (connectedVs[v0].length * rng.nextDouble())];
}
if (v2 == v) {
return;
}

embVs1.clear();
for (int i = 0; i < embVSets[v].length; i++) {
embVs1.add(embVSets[v].values[i]);
}
embVs2.clear();
for (int i = 0; i < embVSets[v2].length; i++) {
embVs2.add(embVSets[v2].values[i]);
}

int beforeV = -100 * connectedVsEmb[v].length;
int beforeV2 = -100 * connectedVsEmb[v2].length;
if (isConnectedEmb[v2][v] >= 0) {
beforeV2 += 100;
}

update(embVs2.values, 0, embVs2.length, EMPTY);
int afterV2 = simulateAdds(embVs1.values, 0, embVs1.length, v2);
int afterV = simulateAdds(embVs2.values, 0, embVs2.length, v);

int newScore = score + beforeV + beforeV2 + afterV + afterV2;

for (int i = change.length - 1; i >= 0; i--) {
int value = change.values[i];
int embR = (value >>> 20) & ((1 << 10) - 1);
int embC = (value >>> 10) & ((1 << 10) - 1);
int v3 = (value >>> 0) & ((1 << 10) - 1);
inverseEmb[embR][embC] = v3;
}
change.clear();
if (newScore >= score || sa.accept(newScore, score)) {
removeAll(v);
removeAll(v2);

adds(embVs1.values, 0, embVs1.length, v2);
adds(embVs2.values, 0, embVs2.length, v);

score = newScore;
saveBest();

}
}

private IntArray[] bestEmbVSets;

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int v = 0; v < NV; v++) {
System.arraycopy(embVSets[v].values, 0, bestEmbVSets[v].values, 0, embVSets[v].length);
bestEmbVSets[v].length = embVSets[v].length;
}
}
}

private void loadBest() {
score = bestScore;
for (int v = 0; v < NV; v++) {
System.arraycopy(bestEmbVSets[v].values, 0, embVSets[v].values, 0, bestEmbVSets[v].length);
embVSets[v].length = bestEmbVSets[v].length;
}
}

private String[] makeSolution() {
String[] res = new String[NV];
for (int v = 0; v < NV; v++) {

IntArray embVSet = embVSets[v];

StringBuilder resV = new StringBuilder();
resV.append(embVSet.length);
for (int i = 0; i < embVSet.length; i++) {
int embV = embVSet.values[i];
resV.append(" " + (embV + 1));
}
res[v] = resV.toString();
}
return res;
}

private boolean isValid(int v, int min, int sup) {
return v >= min && v < sup;
}

private int toEmbV(int embR, int embC) {
return embR * S0 + embC;
}

private int toEmbC(int embV) {
return embV % S0;
}

private int toEmbR(int embV) {
return embV / S0;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

String line = br.readLine();
String[] split = line.split(" ");
int NV = Integer.parseInt(split[0]);
int NE = Integer.parseInt(split[1]);

int[] u = new int[NE];
int[] v = new int[NE];
for (int i = 0; i < NE; i++) {
line = br.readLine();
split = line.split(" ");
u[i] = Integer.parseInt(split[0]);
v[i] = Integer.parseInt(split[1]);
}

line = br.readLine();
split = line.split(" ");
int NEmbV = Integer.parseInt(split[0]);
int NEmbE = Integer.parseInt(split[1]);

int[] a = new int[NEmbE];
int[] b = new int[NEmbE];
for (int i = 0; i < NEmbE; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

Main main = new Main();
String[] ret = main.run(NV, NE, u, v, NEmbV, NEmbE, a, b);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

}

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 Edge {
int u;
int v;

public Edge(int u, int v) {
super();
this.u = u;
this.v = v;
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

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

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index == length) {
add(value);
return;
}

if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

class SAState {

public static final boolean useTime = true;

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

public double startTemperature = 50;
public double endTemperature = 5;
public double temperature = startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 1 << 20;
public double endRange = 1 << 20;
public double range = startRange;

public int loop;
public int countChange;
public int countAccept;

public void init() {
loop = 0;
countChange = 0;
countAccept = 0;
lastAcceptTemperature = startTemperature;
startTime = useTime ? Main.watch.getSecond() : loop;

updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

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

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return Main.rng.nextDouble() < Math.exp((newScore - currentScore) / (temperature));
}

}



Top Coder Marathon Match でいつも競っているみんなと同じような順位で良かった。

上位者がランチョンで表彰されるので、ほとんど AtCoder Open 2017 じゃないかと思った。


Approach 複数の点の位置を決める問題なので、SAでOKでしょう(TCO13 MM R3 2nd place, MM86 1st place, MM92 上位ほぼ全員, TCO17 MM R1 上位ほぼ全員)。


初期解 Full Graph だと思って、有効な辺の数が多くなるように、中央に集めた。

近傍 ある頂点vを選んで、8方向調べて、最も Weight が小さい頂点v2を、vとつながっている頂点v3でswap または move v3 to v2(v2が空の時)。
v3の選び方は、vとつながっている頂点を、Weight順に並べ替えておいて、 v3 = connectedVs[ (int)(connectedVs.length * rng.nextDouble() * rng.nextDouble())] で選んだ。

温度 線形に減らした。
meanEdges < 2のとき、1 -> 0。
meanEdges < 5のとき、meanEdgesが2に近いほど1 -> 0。meanEdgesが5に近いほど2 -> 1。
meanEdges < 10のとき、meanEdgesが5に近いほど2 -> 1。meanEdgesが10に近いほど2.5 -> 1。
meanEdges < 15のとき、meanEdgesが10に近いほど2.5 -> 1。meanEdgesが15に近いほど3 -> 1。
meanEdges < 20のとき、meanEdgesが15に近いほど3 -> 1。meanEdgesが20に近いほど3.5 -> 1。
meanEdges >= 20のとき、3.5 -> 1。


高速化 各頂点ごとに、8方向のWeightの和をおぼえておく。
2次元配列を1次元配列に変える。
頂点ごとのスコア計算する時、8方向を調べるときの for を展開する。
tomerun さんのSAの枝刈り と EvbCFfp1XB さんのSAの受理判定の式変形を使った。
試行回数は5千万から1億回。



source code


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class Main {
private static final int shiftS = 6;
private static final int maxS = (1 << shiftS);
private static final int maskS = ((1 << shiftS) - 1);

private static final int[] dr4 = new int[] { -1, 0, 0, 1, };
private static final int[] dc4 = new int[] { 0, -1, 1, 0, };
private static final int[] dz4 = new int[4];
static {
for (int d = 0; d < dz4.length; d++) {
dz4[d] = z(1 + dr4[d], 1 + dc4[d]) - z(1, 1);
}
}
private static final int[] dr8 = new int[] { 0, -1, -1, -1, 0, 1, 1, 1, };
private static final int[] dc8 = new int[] { -1, -1, 0, 1, 1, 1, 0, -1, };
private static final int[] dz8 = new int[8];
static {
for (int d = 0; d < dz8.length; d++) {
dz8[d] = z(1 + dr8[d], 1 + dc8[d]) - z(1, 1);
}
}

private static final int z(int r, int c) {
return (r << shiftS) | c;
}

private static final int r(int z) {
return z >>> shiftS;
}

private static final int c(int z) {
return z & maskS;
}

private static final int zSentinel(int r, int c) {
return z(r + 1, c + 1);
}

private static final int rSentinel(int z) {
return r(z) - 1;
}

private static final int cSentinel(int z) {
return c(z) - 1;
}

static final Watch watch = new Watch();
static final XorShift rng = new XorShift(System.nanoTime());
private static final int EMPTY = -1;
private static final int WALL = -2;

private int NV;
private boolean[][] hasEdgeEmb;
private Edge[] edges;
private Edge[] edgesEmb;
private int S;
private IntArray[] connectedVs;
private IntArray[] connectedEmbVs;
private int[][] edgeWeight;

private int[] toEmb;
private int[] reverseEmb = new int[maxS * maxS];
private int score;
private int bestScore;
private int minScore;
private IntArray diffFromBest = new IntArray(1 << 20);

private String[] run(int NV, int NE, int[] u, int[] v, int[] w, int NEmbV, int NEmbE, int[] a, int[] b) {
init(NV, NE, u, v, w, NEmbV, NEmbE, a, b);
solve();
return makeSolution();
}

private void init(int NV, int NE, int[] u, int[] v, int[] w, int NEmbV, int NEmbE, int[] a, int[] b) {
this.NV = NV;
for (int i = 0; i < u.length; i++) {
u[i]--;
}
for (int i = 0; i < v.length; i++) {
v[i]--;
}

this.edgeWeight = new int[NV][NV];
for (int i = 0; i < u.length; i++) {
edgeWeight[u[i]][v[i]] = w[i];
edgeWeight[v[i]][u[i]] = w[i];
}

ArrayList<Edge> edges2 = new ArrayList<>();
for (int i = 0; i < u.length; i++) {
if (w[i] == 0) {
continue;
}
edges2.add(new Edge(u[i], v[i], w[i]));
}
Collections.sort(edges2, new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
if (o1.w > o2.w) {
return -1;
}
if (o1.w < o2.w) {
return 1;
}
return 0;
}
});
edges = (Edge[]) edges2.toArray(new Edge[edges2.size()]);

connectedVs = new IntArray[NV];
for (int i = 0; i < connectedVs.length; i++) {
connectedVs[i] = new IntArray();
}
for (int i = 0; i < edges.length; i++) {
connectedVs[edges[i].u].add(edges[i].v);
connectedVs[edges[i].v].add(edges[i].u);
}
for (int i = 0; i < a.length; i++) {
a[i]--;
}
for (int i = 0; i < b.length; i++) {
b[i]--;
}

this.hasEdgeEmb = new boolean[NEmbV][NEmbV];
for (int i = 0; i < a.length; i++) {
hasEdgeEmb[a[i]][b[i]] = true;
hasEdgeEmb[b[i]][a[i]] = true;
}

S = (int) Math.sqrt(NEmbV + 1e-9);
edgesEmb = new Edge[a.length];
for (int i = 0; i < a.length; i++) {
edgesEmb[i] = new Edge(a[i], b[i], 1);
}
connectedEmbVs = new IntArray[NEmbV];
for (int i = 0; i < connectedEmbVs.length; i++) {
connectedEmbVs[i] = new IntArray();
}
for (int i = 0; i < edgesEmb.length; i++) {
connectedEmbVs[edgesEmb[i].u].add(edgesEmb[i].v);
connectedEmbVs[edgesEmb[i].v].add(edgesEmb[i].u);
}
toEmb = new int[NV];
Arrays.fill(reverseEmb, WALL);
for (int r = 0; r < S; r++) {
for (int c = 0; c < S; c++) {
setReverseEmb(r, c, EMPTY);
}
}

Utils.debug("NV", NV, "NE", NE, "NVemb", NEmbV, "NEemb", NEmbE);
isInit = false;
}

private void solve() {
greedyUseNumEdges();

score = calculateScore();
for (int r = 1; r <= S; r++) {
for (int c = 1; c <= S; c++) {
currentPartialScores[z(r, c)] = calculatePartialScore(z(r, c));
}
}

SA();
}

private void greedyUseNumEdges() {
for (int v = 0; v < NV; v++) {
int max = -1;
int maxEmbV = -1;
double minDistance = -1;

LinkedList<Integer> queue = new LinkedList<>();
boolean[][] used = new boolean[S][S];
{
int r = S / 2;
int c = S / 2;
queue.add(z(r, c));
used[r][c] = true;
}
for (; !queue.isEmpty();) {
int currentZ = queue.pollFirst().intValue();
int r = r(currentZ);
int c = c(currentZ);
int embV = zSentinel(r, c);

if (getReverseEmb(r, c) == WALL) {
continue;
}

if (getReverseEmb(r, c) >= 0) {

for (int d = 0; d < dr4.length; d++) {
int nr = r + dr4[d];
int nc = c + dc4[d];
if (nr < 0 || nr >= S) {
continue;
}
if (nc < 0 || nc >= S) {
continue;
}
if (used[nr][nc]) {
continue;
}
queue.add(z(nr, nc));
used[nr][nc] = true;
}

continue;
}

int score = 0;
for (int d = 0; d < dr8.length; d++) {
int nr = r + dr8[d];
int nc = c + dc8[d];
if (nr < 0 || nr >= S) {
continue;
}
if (nc < 0 || nc >= S) {
continue;
}
if (getReverseEmb(nr, nc) >= 0) {
score++;
}
}
double distance = euclideanDistance(r, c, S / 2, S / 2);
if (score > max) {
max = score;
maxEmbV = embV;
minDistance = distance;
} else if (score == max && distance < minDistance) {
max = score;
maxEmbV = embV;
minDistance = distance;
}
}
setReverseEmb(maxEmbV, v);
toEmb[v] = maxEmbV;
assert maxEmbV == toEmb[v] : Utils.toString(maxEmbV, toEmb[v]);
assert reverseEmb[maxEmbV] == v : Utils.toString(reverseEmb[maxEmbV], v);
}
}

private static final double euclideanDistance(double r1, double c1, double r2, double c2) {
double deltaR = r2 - r1;
double deltaC = c2 - c1;
return Math.sqrt(deltaR * deltaR + deltaC * deltaC);
}

private SAState sa = new SAState();

private void SA() {

double second = 1;
int mask = (1 << 18) - 1;

sa.init();

double minEdges = ((double) NV - 1) / NV;
double meanEdges = (double) edges.length / NV;
if (meanEdges < 2) {
sa.startTemperature = interpolate(1.0, 1.0, 2.0, meanEdges, minEdges);
sa.endTemperature = interpolate(0.0, 0.0, 2.0, meanEdges, minEdges);
} else if (meanEdges < 5) {
sa.startTemperature = interpolate(1.0, 2, 5.0, meanEdges, minEdges);
sa.endTemperature = interpolate(0.0, 1.0, 5.0, meanEdges, minEdges);
} else if (meanEdges < 10) {
sa.startTemperature = interpolate(2.0, 2.5, 10.0, meanEdges, minEdges);
sa.endTemperature = interpolate(1.0, 1.0, 10.0, meanEdges, minEdges);
} else if (meanEdges < 15) {
sa.startTemperature = interpolate(2.5, 3.0, 15.0, meanEdges, minEdges);
sa.endTemperature = interpolate(1.0, 1.0, 15.0, meanEdges, minEdges);
} else if (meanEdges < 20) {
sa.startTemperature = interpolate(3.0, 3.5, 20.0, meanEdges, minEdges);
sa.endTemperature = interpolate(1.0, 1.0, 20.0, meanEdges, minEdges);
} else {
sa.startTemperature = interpolate(3.5, 3.5, 100.0, meanEdges, minEdges);
sa.endTemperature = interpolate(1.0, 1.0, 100.0, meanEdges, minEdges);
}

Utils.debug(sa.startTemperature, sa.endTemperature);

for (;; sa.loop++) {
if ((sa.loop & mask) == 0) {
sa.updateTime();

if (sa.isTLE()) {
loadBest();
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5d", minScore), String.format("%5d", score), String.format("%5d", bestScore), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastAcceptTemperature));
break;
}

sa.updateTemperature();

if (sa.time > second) {
second++;
Utils.debug(sa.loop, String.format("%.2f%%", 100.0 * sa.countChange / sa.loop), String.format("%.2f%%", 100.0 * sa.countAccept / sa.countChange), String.format("%5d", minScore), String.format("%5d", score), String.format("%5d", bestScore), String.format("%.6f", sa.temperature), String.format("%.6f", sa.lastAcceptTemperature));
}
}

swapMinWeight();
minScore = Math.min(minScore, score);
}
}

private double interpolate(double minTemperature, double maxTemperature, double maxEdges, double meanEdges, double minEdges) {
return minTemperature + (maxTemperature - minTemperature) * ((meanEdges - minEdges) / (maxEdges - minEdges));
}

private IntArray minWeigthVs = new IntArray(8);

private int vi = 0;

private void swapMinWeight() {
vi++;
if (vi >= NV) {
vi = 0;
}

int v = vi;

int embV = toEmb[v];
assert reverseEmb[embV] == v : Utils.toString(reverseEmb[embV], v);

int minWeigth = 16;
minWeigthVs.clear();
for (int d = 0; d < dz8.length; d++) {
int nextEmbV = embV + dz8[d];
int nv = reverseEmb[nextEmbV];
if (nv == WALL) {
continue;
}

int weight = nv < 0 ? 0 : edgeWeight[nv][v];
if (weight < minWeigth) {
minWeigth = weight;
minWeigthVs.clear();
minWeigthVs.add(nextEmbV);
} else if (weight == minWeigth) {
minWeigthVs.add(nextEmbV);
}
}

int n = minWeigthVs.values[(int) (minWeigthVs.length * rng.nextDouble())];
int nv = reverseEmb[n];

int v2 = connectedVs[v].values[(int) (connectedVs[v].length * rng.nextDouble() * rng.nextDouble())];
if (v2 == nv) {
for (int k = 0; k < 3; k++) {
v2 = connectedVs[v].values[(int) (connectedVs[v].length * rng.nextDouble() * rng.nextDouble())];
if (v2 != nv) {
break;
}
}
if (v2 == nv) {
return;
}
}

if (nv == -1) {
move(nv, v2, n, toEmb[v2]);
} else {
assert v2 != nv;
swap(nv, v2, toEmb[nv], toEmb[v2]);
}
}

private int getReverseEmb(int embR, int embC) {
return reverseEmb[z(embR + 1, embC + 1)];
}

private int setReverseEmb(int embR, int embC, int v) {
return setReverseEmb(z(embR + 1, embC + 1), v);
}

private boolean isInit = true;

private int setReverseEmb(int z, int v) {
if (!isInit)
assert reverseEmb[z] != WALL : Utils.toString(r(z), c(z), reverseEmb[z]);
return reverseEmb[z] = v;
}

private int[] currentPartialScores = new int[maxS * maxS];

private void move(int v, int v2, int embV, int embV2) {
int before = currentPartialScores[embV2];

setReverseEmb(embV, v2);
setReverseEmb(embV2, v);

int after = calculatePartialScore(embV);
int after2 = 0;

int newScore = score - before + after;

sa.countChange++;
if (newScore >= score || sa.accept(newScore, score)) {
sa.countAccept++;
if (!(newScore >= score)) {
sa.lastAcceptTemperature = sa.temperature;
}
score = newScore;

{
if (score >= bestScore) {
bestScore = score;
diffFromBest.clear();
} else {
diffFromBest.add((v2) | (toEmb[v2] << 10));
}
}

toEmb[v2] = embV;
updateCurrentPartialScore(embV, v2, v);
updateCurrentPartialScore(embV2, v, v2);

currentPartialScores[embV] = after;
currentPartialScores[embV2] = after2;
} else {
setReverseEmb(embV, v);
setReverseEmb(embV2, v2);
}
}

private void swap(int v, int v2, int embV, int embV2) {
int before = currentPartialScores[embV] + currentPartialScores[embV2];

setReverseEmb(embV, v2);
setReverseEmb(embV2, v);

int after = calculatePartialScore(embV);
int after2 = calculatePartialScore(embV2);

int newScore = score - before + after + after2;

sa.countChange++;
if (newScore >= score || sa.accept(newScore, score)) {
sa.countAccept++;
if (!(newScore >= score)) {
sa.lastAcceptTemperature = sa.temperature;
}

score = newScore;

{
if (score >= bestScore) {
if (score > bestScore) {
minScore = bestScore;
}
bestScore = score;
diffFromBest.clear();
} else {
diffFromBest.add((v2) | (toEmb[v2] << 10));
diffFromBest.add((v) | (toEmb[v] << 10));
}
}

toEmb[v2] = embV;
toEmb[v] = embV2;
updateCurrentPartialScore(embV, v2, v);
updateCurrentPartialScore(embV2, v, v2);

currentPartialScores[embV] = after;
currentPartialScores[embV2] = after2;
} else {
setReverseEmb(embV, v);
setReverseEmb(embV2, v2);
}
}

private void updateCurrentPartialScore(int embV, int newV, int oldV) {
for (int d = 0; d < dr8.length; d++) {
int nextEmbV = embV + dz8[d];
if (reverseEmb[nextEmbV] == WALL) {
continue;
}
int nextV = reverseEmb[nextEmbV];
if (nextV < 0) {
continue;
}
currentPartialScores[nextEmbV] += -(oldV == -1 ? 0 : edgeWeight[oldV][nextV]) + (newV == -1 ? 0 : edgeWeight[newV][nextV]);
}
}

private int calculateScore() {
int score = 0;
for (int v = 0; v < NV; v++) {
int embR = r(toEmb[v]);
int embC = c(toEmb[v]);
score += calculatePartialScore(z(embR, embC));
}
return score >>> 1;
}

private static final int d0 = 0;
private static final int d1 = 1;
private static final int d2 = 2;
private static final int d3 = 3;
private static final int d4 = 4;
private static final int d5 = 5;
private static final int d6 = 6;
private static final int d7 = 7;

private int calculatePartialScore(int embV) {
assert reverseEmb[embV] != WALL;
if (reverseEmb[embV] < 0) {
return 0;
}

int score = 0;

int v = reverseEmb[embV];
{
int nextV = reverseEmb[embV + dz8[d0]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d1]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d2]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d3]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d4]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d5]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d6]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}
{
int nextV = reverseEmb[embV + dz8[d7]];
if (nextV >= 0) {
score += edgeWeight[nextV][v];
}
}

return score;
}

private void loadBest() {
score = bestScore;
for (int i = diffFromBest.length - 1; i >= 0; i--) {
int value = diffFromBest.values[i];
int v = (value >>> 0) & ((1 << 10) - 1);
int toEmb = (value >>> 10);
this.toEmb[v] = toEmb;
}
}

private String[] makeSolution() {
String[] res = new String[NV];
for (int v = 0; v < NV; v++) {
int embR = rSentinel(toEmb[v]);
int embC = cSentinel(toEmb[v]);
res[v] = "" + (v + 1) + " " + ((embR * S + embC) + 1);
}
return res;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

String line = br.readLine();
String[] split = line.split(" ");
int V = Integer.parseInt(split[0]);
int E = Integer.parseInt(split[1]);

int[] u = new int[E];
int[] v = new int[E];
int[] w = new int[E];
for (int i = 0; i < E; i++) {
line = br.readLine();
split = line.split(" ");
u[i] = Integer.parseInt(split[0]);
v[i] = Integer.parseInt(split[1]);
w[i] = Integer.parseInt(split[2]);
}

line = br.readLine();
split = line.split(" ");
int Vemb = Integer.parseInt(split[0]);
int Eemb = Integer.parseInt(split[1]);

int[] a = new int[Eemb];
int[] b = new int[Eemb];
for (int i = 0; i < Eemb; i++) {
line = br.readLine();
split = line.split(" ");
a[i] = Integer.parseInt(split[0]);
b[i] = Integer.parseInt(split[1]);
}

Main main = new Main();
String[] ret = main.run(V, E, u, v, w, Vemb, Eemb, a, b);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}

}

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 Edge {
int u;
int v;
int w;

public Edge(int u, int v, int w) {
super();
this.u = u;
this.v = v;
this.w = w;
}

}

class IntArray {
public int[] values;
public int length;

public IntArray() {
this(new int[4], 0);
}

public IntArray(int capacity) {
this(new int[capacity], 0);
}

public IntArray(int[] values) {
this(values, values.length);
}

public IntArray(int[] values, int length) {
this.values = values;
this.length = length;
}

public void add(int value) {
if (length == values.length) {
values = Arrays.copyOf(values, values.length << 1);
}
values[length++] = value;
}

public int remove() {
return values[--length];
}

public boolean contains(int value) {
for (int i = 0; i < length; i++) {
if (values[i] == value) {
return true;
}
}
return false;
}

public void clear() {
length = 0;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < length; i++) {
sb.append(values[i] + ",");
}
sb.append("}");
return sb.toString();
}

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

public int remove(int index) {
if (index >= length) {
throw new AssertionError();
}

if (index == length - 1) {
return remove();
}

int res = values[index];
System.arraycopy(values, index + 1, values, index, length - (index + 1));
length--;

return res;
}

public void set(int index, int value) {
if (index == length) {
add(value);
return;
}

if (index >= length) {
throw new AssertionError();
}

if (length >= values.length - 1) {
values = Arrays.copyOf(values, values.length << 1);
}
System.arraycopy(values, index, values, index + 1, length - index);
length++;

values[index] = value;
}

public IntArray copy() {
return new IntArray(Arrays.copyOf(values, length), length);
}

public int[] toArray() {
return Arrays.copyOf(values, length);
}

}

class SAState {

public static final boolean useTime = true;

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

public double startTemperature = 3.5;
public double endTemperature = 1.0;
public double temperature = startTemperature;
public double lastAcceptTemperature = startTemperature;

public double startRange = 1 << 20;
public double endRange = 1 << 20;
public double range = startRange;

public int loop;
public int countChange;
public int countAccept;

public void init() {
loop = 0;
countChange = 0;
countAccept = 0;
lastAcceptTemperature = startTemperature;
startTime = useTime ? Main.watch.getSecond() : loop;

updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
temperature = endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

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

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

public boolean accept(double newScore, double currentScore) {
assert newScore - currentScore < 0;
assert temperature >= 0;
return (newScore - currentScore > -10 * (temperature) && (Main.rng.nextInt() & 2147483647) < 1 << (int) (31.5 + (newScore - currentScore) / (temperature)));
}

}




このページのトップヘ