EvbCFfp1XB

problem and my answer.



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

}





最終日に2時間ほど参加して、一瞬参加したというchokudaiさんに勝ててよかった。


Rank 985/2512


Approach レイジが60以上の時5%の確率でスキルを使う。
それ以外は、Nearest Neighbor。



source code

import java.util.*;
import java.io.*;
import java.math.*;

/**
* Auto-generated code below aims at helping you parse the standard input according to the problem statement.
**/
class Player {

public static void main(String args[]) {
Scanner in = new Scanner(System.in);

// game loop
while (true) {
int myScore = in.nextInt();
int enemyScore1 = in.nextInt();
int enemyScore2 = in.nextInt();

int myRage = in.nextInt();
int enemyRage1 = in.nextInt();
int enemyRage2 = in.nextInt();

int unitCount = in.nextInt();

ArrayList<Reaper> reapers = new ArrayList<>();
ArrayList<Destroyer> destroyers = new ArrayList<>();
ArrayList<Doof> doofs = new ArrayList<>();
ArrayList<Tanker> tankers = new ArrayList<>();
ArrayList<Wreck> wrecks = new ArrayList<>();
for (int i = 0; i < unitCount; i++) {
int unitId = in.nextInt();
int unitType = in.nextInt();
int player = in.nextInt();
float mass = in.nextFloat();
int radius = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
int vx = in.nextInt();
int vy = in.nextInt();
int extra = in.nextInt();
int extra2 = in.nextInt();

if (unitType == 0) {
Reaper reaper = new Reaper();
reaper.unitId = unitId;
reaper.unitType = unitType;
reaper.player = player;
reaper.mass = mass;
reaper.radius = radius;

reaper.x = x;
reaper.y = y;
reaper.vx = vx;
reaper.vy = vy;
reaper.extra = extra;
reaper.extra2 = extra2;
reapers.add(reaper);
} else if (unitType == 1) {
Destroyer destroyer = new Destroyer();
destroyer.unitId = unitId;
destroyer.unitType = unitType;
destroyer.player = player;
destroyer.mass = mass;
destroyer.radius = radius;

destroyer.x = x;
destroyer.y = y;
destroyer.vx = vx;
destroyer.vy = vy;
destroyer.extra = extra;
destroyer.extra2 = extra2;
destroyers.add(destroyer);
} else if (unitType == 2) {
Doof doof = new Doof();
doof.unitId = unitId;
doof.unitType = unitType;
doof.player = player;
doof.mass = mass;
doof.radius = radius;

doof.x = x;
doof.y = y;
doof.vx = vx;
doof.vy = vy;
doof.extra = extra;
doof.extra2 = extra2;
doofs.add(doof);
} else if (unitType == 3) {
Tanker tanker = new Tanker();
tanker.unitId = unitId;
tanker.unitType = unitType;
tanker.player = player;
tanker.mass = mass;
tanker.radius = radius;

tanker.x = x;
tanker.y = y;
tanker.vx = vx;
tanker.vy = vy;
tanker.extra = extra;
tanker.extra2 = extra2;
tankers.add(tanker);
} else if (unitType == 4) {
Wreck wreck = new Wreck();
wreck.unitId = unitId;
wreck.unitType = unitType;
wreck.player = player;
wreck.mass = mass;
wreck.radius = radius;

wreck.x = x;
wreck.y = y;
wreck.vx = vx;
wreck.vy = vy;
wreck.extra = extra;
wreck.extra2 = extra2;
wrecks.add(wreck);
}
}

// Write an action using System.out.println()
// To debug: System.err.println("Debug messages...");

String reaperCommand = "WAIT";
String destroyerCommand = "WAIT";
String doofCommand = "WAIT";

Tanker minDistanceTanker = null;
for (Destroyer destroyer : destroyers) {
if (destroyer.player == 0) {
double minDistance = 1e9;
for (Tanker tanker : tankers) {
// int dy = destroyer.y - tanker.y;
// int dx = destroyer.x - tanker.x;
int dy = 0 - tanker.y;
int dx = 0 - tanker.x;
double distance = Math.sqrt(dx * dx + dy * dy);
if (distance < minDistance) {
minDistance = distance;
minDistanceTanker = tanker;
}
}
if (minDistanceTanker == null) {
continue;
}
if (myRage >= 60 && Math.random() < 0.05) {
destroyerCommand = ("SKILL " + minDistanceTanker.x + " " + minDistanceTanker.y);
} else {
destroyerCommand = ("" + minDistanceTanker.x + " " + minDistanceTanker.y + " " + 300);
}
}
}

for (Doof doof : doofs) {
if (doof.player == 0) {
double minDistance = 1e9;
Reaper minDistanceReaper = null;
for (Reaper reaper : reapers) {
if (reaper.player == 0) {
continue;
}
int dy = doof.y - reaper.y;
int dx = doof.x - reaper.x;
double distance = Math.sqrt(dx * dx + dy * dy);
if (distance < minDistance) {
minDistance = distance;
minDistanceReaper = reaper;
}
}
if (minDistanceReaper == null) {
continue;
}
if (myRage >= 60 && Math.random() < 0.05) {
doofCommand = ("SKILL " + minDistanceReaper.x + " " + minDistanceReaper.y);
} else {
doofCommand = ("" + minDistanceReaper.x + " " + minDistanceReaper.y + " " + 300);
}
// Tanker minDistanceTanker = null;
// for (Tanker tanker : tankers) {
// int dy = doof.y - tanker.y;
// int dx = doof.x - tanker.x;
// double distance = Math.sqrt(dx * dx + dy * dy);
// if (distance < minDistance) {
// minDistance = distance;
// minDistanceTanker = tanker;
// }
// }
// if (minDistanceTanker == null) {
// continue;
// }
// System.out.println("" + minDistanceTanker.x + " " + minDistanceTanker.y + " " + 300);
}
}

for (Reaper reaper : reapers) {
if (reaper.player == 0) {
double minDistance = 1e9;
Wreck minDistanceWreck = null;
for (Wreck wreck : wrecks) {
int dy = reaper.y - wreck.y;
int dx = reaper.x - wreck.x;
double distance = Math.sqrt(dx * dx + dy * dy);
if (distance < minDistance) {
minDistance = distance;
minDistanceWreck = wreck;
}
}
if (minDistanceWreck == null) {
if (minDistanceTanker == null) {
continue;
}
if (myRage >= 60 && Math.random() < 0.05) {
reaperCommand = ("SKILL " + minDistanceTanker.x + " " + minDistanceTanker.y);
} else {
reaperCommand = ("" + minDistanceTanker.x + " " + minDistanceTanker.y + " " + 300);
}
continue;
}
if (myRage >= 60 && Math.random() < 0.05) {
reaperCommand = ("SKILL " + minDistanceWreck.x + " " + minDistanceWreck.y);
} else {
reaperCommand = ("" + minDistanceWreck.x + " " + minDistanceWreck.y + " " + 300);
}
}
}

System.out.println(reaperCommand);
System.out.println(destroyerCommand);
System.out.println(doofCommand);

// for (int i = print; i < 3; i++) {
// System.out.println("WAIT");
// }
// System.out.println("WAIT");
// System.out.println("WAIT");
// System.out.println("WAIT");
}
}
}

class Wreck {

public int extra2;
public int extra;
public int vy;
public int vx;
public int y;
public int x;
public int radius;
public float mass;
public int player;
public int unitType;
public int unitId;

}

class Reaper {

public int extra2;
public int extra;
public int vy;
public int vx;
public int y;
public int x;
public int radius;
public float mass;
public int player;
public int unitType;
public int unitId;

}

class Destroyer {
public int extra2;
public int extra;
public int vy;
public int vx;
public int y;
public int x;
public int radius;
public float mass;
public int player;
public int unitType;
public int unitId;

}

class Tanker {
public int extra2;
public int extra;
public int vy;
public int vx;
public int y;
public int x;
public int radius;
public float mass;
public int player;
public int unitType;
public int unitId;

}

class Doof {
public int extra2;
public int extra;
public int vy;
public int vx;
public int y;
public int x;
public int radius;
public float mass;
public int player;
public int unitType;
public int unitId;

}





Approach テンプレートマッチングや機械学習を試したが、ベースラインソリューションの tesseract-ocr がよくできていた。
README.md には

Future improvements

  • Increase OCR matches maybe by removing grid lines and ability to recognize hand-written text (could take a lot of effort tuning train/test set)
と書いてあったので、他の参加者は試したのかな?

このページのトップヘ