EvbCFfp1XB

problem and my answer.

March 2019



Approach 無効な状態を許容する焼きなまし法です。

  • 近傍1 : ランダムに route を選んで、使ってなければ追加、そうでなければ削除する
  • 近傍2 : 使っている route を削除して、使ってない route を追加する
  • 近傍3 : ある辺を通っている route を全部削除して、使ってない route を追加する
  • 近傍4 : ある辺を通っている route を全部削除して、追加しなおす(追加する順番はシャッフルする)
    • ここまでやってもまだ seed 1 で、スコアが 2184 にならない。
  • 近傍5 : ある辺を通っている route を全部削除して、追加しなおす(追加する順番はシャッフルする、追加する経路にその辺を使わない)
  • 近傍選択の重み付け : (近傍1 : 近傍2 : 近傍3 : 近傍4 : 近傍5) = (4 : 2 : 1 : 1 : 1)
  • スコア
    • Connections score のボーナス : 使った materials が NM より少ない時は、NM まで使ったときのスコアを予想するために、貪欲法で使ってない辺で points/material が大きいものから使ったことにする
      • 効果1 : スコアの変化が小さくなり、探索空間がなだらかになる
      • 効果2 : materials をいくつ使うかという最適化をする必要がなくなる
    • Connections score のペナルティ : 使った materials が NM より多い時は、(p == 1 ? 10 : 5) * p * p を減らす。ただし、p = 使った materials - NM
  • route を追加するときは、毎回ダイクストラ法を実行する。materials が少ない経路、materials  が同じなら points が大きい経路を優先する。すでに使っている辺を通るときは、materials, points は共に0 で通る。
  • 高速化 : 色々なダイクストラ高速化の、キューを複数用意する高速化を使いました。
  • 焼きなまし法で materials があまれば、ボーナスの貪欲法で辺を追加した後、辺を flip する焼きなまし法を使います。

感想 あと1%は何だろう? materials=1,points=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.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class RoadNetwork {
private int numCities;
private int numMaterials;
private Edge[] edges;
private Route[] routes;

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

private int score;
private int bestScore;
private boolean[] bestSolution;
private boolean[] remainderSolution;
private boolean[] bestRemainderSolution;

private int routeScore;
private int usedMaterials;
private int edgeScore;
private int bestEdgeScore;
private int usedRoutesSize;

private ArrayList<Edge2>[] adjacentCities;

private IntSet[] edgeIndexToUsedRoutes;
private ArrayList<Node>[] routeToNodes;
private IntSet usedRoutes;
private IntSet unusedRoutes;

private int[] countAC = new int[10];
private int[] sumDeltaScore = new int[10];
private ArrayList<Pair<Double, Integer>> rateAndIndexPairs = new ArrayList<>();

private int calculateRouteScore() {
int score = 0;
for (int i = 0; i < usedRoutes.size(); i++) {
int routeIndex = usedRoutes.get(i);
score += routes[routeIndex].points;
}
return score;
}

private int calculateEdgeScorePlus() {
int score = 0;
int usedMaterials = 0;
for (int ei = 0; ei < edgeIndexToUsedRoutes.length; ei++) {
if (edgeIndexToUsedRoutes[ei].size() == 0) {
continue;
}
Edge edge = edges[ei];
score += edge.points;
usedMaterials += edge.dist;
}

if (usedMaterials < numMaterials) {
for (int i = 0; i < rateAndIndexPairs.size(); i++) {
int ei = rateAndIndexPairs.get(i).second.intValue();
if (edgeIndexToUsedRoutes[ei].size() > 0) {
continue;
}
Edge edge = edges[ei];
if (usedMaterials + edge.dist > numMaterials) {
continue;
}
score += edge.points;
usedMaterials += edge.dist;
if (usedMaterials >= numMaterials) {
break;
}
}
return score;
}

int p = usedMaterials - numMaterials;
score += (p == 1 ? -10 : -5) * p * p;
return score;
}

private int calculatePlus() {
int score = 0;
int usedMaterials = 0;
for (int ei = 0; ei < edgeIndexToUsedRoutes.length; ei++) {
if (edgeIndexToUsedRoutes[ei].size() == 0) {
continue;
}
Edge edge = edges[ei];
usedMaterials += edge.dist;
}

if (usedMaterials < numMaterials) {
for (int i = 0; i < rateAndIndexPairs.size(); i++) {
int ei = rateAndIndexPairs.get(i).second.intValue();
if (edgeIndexToUsedRoutes[ei].size() > 0) {
continue;
}
Edge edge = edges[ei];
if (usedMaterials + edge.dist > numMaterials) {
continue;
}
score += edge.points;
usedMaterials += edge.dist;
if (usedMaterials >= numMaterials) {
break;
}
}
return score;
}

score += -10 * (usedMaterials - numMaterials);
return score;
}

private int calculateEdgeScore() {
int score = 0;
for (int ei = 0; ei < edgeIndexToUsedRoutes.length; ei++) {
if (edgeIndexToUsedRoutes[ei].size() == 0) {
continue;
}
Edge edge = edges[ei];
score += edge.points;
}
return score;
}

private int calculateUsedMaterials() {
int usedMaterials = 0;
for (int ei = 0; ei < edgeIndexToUsedRoutes.length; ei++) {
if (edgeIndexToUsedRoutes[ei].size() == 0) {
continue;
}
Edge edge = edges[ei];
usedMaterials += edge.dist;
}
return usedMaterials;
}

public int[] findSolution(int NumMaterials, int N, int E, String[] edges, int R, String[] routes) {
init(NumMaterials, N, E, edges, R, routes);
solve();
Utils.debug("countAC", countAC);
Utils.debug("sumDeltaScore", sumDeltaScore);
return makeSolution();
}

private void init(int NumMaterials, int N, int E, String[] edges2, int R, String[] routes2) {
numMaterials = NumMaterials;
numCities = N;
edges = new Edge[edges2.length];
for (int ei = 0; ei < edges2.length; ei++) {
String[] split = edges2[ei].split(" ");
edges[ei] = new Edge(Integer.parseInt(split[0]), Integer.parseInt(split[1]), Integer.parseInt(split[2]), Integer.parseInt(split[3]));
}
routes = new Route[routes2.length];
for (int ri = 0; ri < routes2.length; ri++) {
String[] split = routes2[ri].split(" ");
routes[ri] = new Route(Integer.parseInt(split[0]), Integer.parseInt(split[1]), Integer.parseInt(split[2]));
}

adjacentCities = new ArrayList[numCities];
for (int i = 0; i < adjacentCities.length; i++) {
adjacentCities[i] = new ArrayList<>();
}
for (int i = 0; i < edges.length; i++) {
Edge edge = edges[i];
adjacentCities[edge.a].add(new Edge2(i, edge.b, edge.dist, edge.points));
adjacentCities[edge.b].add(new Edge2(i, edge.a, edge.dist, edge.points));
}

edgeIndexToUsedRoutes = new IntSet[edges.length];
for (int i = 0; i < edgeIndexToUsedRoutes.length; i++) {
edgeIndexToUsedRoutes[i] = new IntSet(routes.length + 1);
}

routeToNodes = new ArrayList[routes.length];
for (int i = 0; i < routeToNodes.length; i++) {
routeToNodes[i] = new ArrayList<>();
}

usedRoutes = new IntSet(routes.length);
unusedRoutes = new IntSet(routes.length);
for (int i = 0; i < routes.length; i++) {
unusedRoutes.add(i);
}

{
for (int ei = 0; ei < edges.length; ei++) {
rateAndIndexPairs.add(new Pair<Double, Integer>(edges[ei].points * -1.0 / edges[ei].dist, ei));
}
Collections.sort(rateAndIndexPairs);

double sumEdgePoints = 0;
double sumMaterials = 0;
for (int i = 0; i < rateAndIndexPairs.size(); i++) {
int ei = rateAndIndexPairs.get(i).second.intValue();
if (sumMaterials + edges[ei].dist <= numMaterials) {
sumMaterials += edges[ei].dist;
sumEdgePoints += edges[ei].points;
}
}

sa.startTemperature = sumEdgePoints * 4;
}

bestSolution = new boolean[edges.length];
remainderSolution = new boolean[edges.length];
bestRemainderSolution = new boolean[edges.length];

isAvailable = new boolean[edges.length];
Arrays.fill(isAvailable, true);

minDist = new int[numCities];
maxPoints = new int[numCities];

Utils.debug("materials", numMaterials, "cities", numCities, "edges", edges.length, "routes", routes.length);
}

private void solve() {
sa.endTime = 9.0;
SA();
sa.endTime = 9.8;
remainderSA();
}

private void SA() {
double second = Math.ceil(watch.getSecond());
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 5) - 1)) == 0) {
sa.update();

if (sa.isTLE()) {
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%d", score), String.format("%d", calculateEdgeScore()), String.format("%d", calculateEdgeScorePlus()), String.format("%d", calculatePlus()), String.format("%d", calculateRouteScore()), String.format("%d", calculateEdgeScorePlus() * calculateRouteScore()), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}

if (sa.time > 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("%d", score), String.format("%d", calculateEdgeScore()), String.format("%d", calculateEdgeScorePlus()), String.format("%d", calculatePlus()), String.format("%d", calculateRouteScore()), String.format("%d", calculateEdgeScorePlus() * calculateRouteScore()), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

mutate();
}

Utils.debug("usedMaterials", usedMaterials, "usedRoutes", usedRoutesSize, "EdgeScore", edgeScore, "RouteScore", routeScore);
bestScore = edgeScore * routeScore;
Utils.debug("SA", "bestScore", bestScore, edgeScore * routeScore, "time", watch.getSecondString());
}

private void remainderSA() {
double second = Math.ceil(watch.getSecond());

score = bestScore;
bestScore = -1;
remainderSaveBest();
{
edgeScore = 0;
usedMaterials = 0;
for (int ei = 0; ei < bestSolution.length; ei++) {
if (!bestSolution[ei]) {
continue;
}
Edge edge = edges[ei];
edgeScore += edge.points;
usedMaterials += edge.dist;
}

if (usedMaterials < numMaterials) {
for (int i = 0; i < rateAndIndexPairs.size(); i++) {
int ei = rateAndIndexPairs.get(i).second.intValue();
if (bestSolution[ei]) {
continue;
}
Edge edge = edges[ei];
if (usedMaterials + edge.dist > numMaterials) {
continue;
}
edgeScore += edge.points;
usedMaterials += edge.dist;
remainderSolution[ei] = true;
if (usedMaterials >= numMaterials) {
break;
}
}
}
score = edgeScore * routeScore;
Utils.debug("score", score, "edgeScore", edgeScore, "routeScore", routeScore);
remainderSaveBest();
}

sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();

if (sa.isTLE()) {
remainderLoadBest();
Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%d", score), String.format("%d", calculateEdgeScore()), String.format("%d", calculateEdgeScorePlus()), String.format("%d", calculatePlus()), String.format("%d", calculateRouteScore()), String.format("%d", calculateEdgeScorePlus() * calculateRouteScore()), String.format("%d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
break;
}

if (sa.time > 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("%10d", score), String.format("%10d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
}
}

remainderMutate();
}

Utils.debug("usedMaterials", usedMaterials, "usedRoutes", usedRoutesSize, "EdgeScore", edgeScore, "RouteScore", routeScore);
Utils.debug("SA", "bestScore", bestScore, bestEdgeScore * routeScore, "time", watch.getSecondString());
}

private void mutate() {
double random = 9 * rng.nextDouble();
if (random < 4) {
flipRoute(0);
} else if (random < 6) {
removeAndAddRoute(2);
} else if (random < 7) {
removeAndAddRouteInAnEdge(3);
} else if (random < 8) {
removeAndAddSameRoutesInAnEdge(4);
} else if (random < 9) {
removeAndAddSubPath(6);
}
}

private void remainderMutate() {
flipEdge(5);
}

private void removeRoute(int i) {

if (usedRoutes.size() == 0) {
return;
}
int routeIndex = usedRoutes.get((int) (usedRoutes.size() * rng.nextDouble()));

ArrayList<Node> nodes = routeToNodes[routeIndex];
assert nodes != null;
remove(routeIndex, nodes);

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;
routeToNodes[routeIndex] = null;

saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
add(routeIndex, nodes);
}
}

private void addRoute(int i) {

if (unusedRoutes.size() == 0) {
return;
}
int routeIndex = unusedRoutes.get((int) (unusedRoutes.size() * rng.nextDouble()));

ArrayList<Node> nodes = search(routeIndex);
if (nodes == null) {
return;
}

add(routeIndex, nodes);

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;

routeToNodes[routeIndex] = nodes;
saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
remove(routeIndex, nodes);
}

}

private void flipRoute(int i) {

int routeIndex = (int) (routes.length * rng.nextDouble());
if (usedRoutes.contains(routeIndex)) {

ArrayList<Node> nodes = routeToNodes[routeIndex];
assert nodes != null;
remove(routeIndex, nodes);

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;
routeToNodes[routeIndex] = null;

saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
add(routeIndex, nodes);
}
} else {

ArrayList<Node> nodes = search(routeIndex);
if (nodes == null) {
return;
}

add(routeIndex, nodes);

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;

routeToNodes[routeIndex] = nodes;
saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
remove(routeIndex, nodes);
}
}
}

private void removeAndAddRoute(int i) {

int routeIndexRemove = -1;
if (usedRoutes.size() > 0) {
routeIndexRemove = usedRoutes.get((int) (usedRoutes.size() * rng.nextDouble()));
}
int routeIndexAdd = -1;
if (unusedRoutes.size() > 0) {
routeIndexAdd = unusedRoutes.get((int) (unusedRoutes.size() * rng.nextDouble()));
}

ArrayList<Node> nodesRemove = null;
if (routeIndexRemove != -1) {
nodesRemove = routeToNodes[routeIndexRemove];
if (nodesRemove != null) {
remove(routeIndexRemove, nodesRemove);
}
}

ArrayList<Node> nodesAdd = null;
if (routeIndexAdd != -1) {
nodesAdd = search(routeIndexAdd);
if (nodesAdd != null) {
add(routeIndexAdd, nodesAdd);
}
}

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;
if (routeIndexRemove != -1) {
routeToNodes[routeIndexRemove] = null;
}
if (routeIndexAdd != -1 && nodesAdd != null) {
routeToNodes[routeIndexAdd] = nodesAdd;
}
saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
if (routeIndexRemove != -1 && nodesRemove != null) {
add(routeIndexRemove, nodesRemove);
}
if (routeIndexAdd != -1 && nodesAdd != null) {
remove(routeIndexAdd, nodesAdd);
}
}

}

private void removeAndAddSameRoute(int i) {
if (usedRoutes.size() == 0) {
return;
}
int routeIndex = usedRoutes.get((int) (usedRoutes.size() * rng.nextDouble()));

ArrayList<Node> nodesRemove = null;
nodesRemove = routeToNodes[routeIndex];
remove(routeIndex, nodesRemove);

ArrayList<Node> nodesAdd = null;
nodesAdd = search(routeIndex);
if (nodesAdd == null) {
add(routeIndex, nodesRemove);
return;
}

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
int usedMaterials = calculateUsedMaterials();
if (usedMaterials <= numMaterials && sa.accept(deltaScore)) {
this.score += deltaScore;
routeToNodes[routeIndex] = nodesAdd;
saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
remove(routeIndex, nodesAdd);
add(routeIndex, nodesRemove);
}

}

private void removeAndAddRouteInAnEdge(int i) {

ArrayList<Integer> routeIndexesRemove = new ArrayList<>();
if (usedRoutes.size() > 0) {
int edgeIndex = (int) (edges.length * rng.nextDouble());
while (edgeIndexToUsedRoutes[edgeIndex].size() == 0) {
edgeIndex = (int) (edges.length * rng.nextDouble());
}
for (int j = 0; j < edgeIndexToUsedRoutes[edgeIndex].size(); j++) {
int e = edgeIndexToUsedRoutes[edgeIndex].get(j);
assert usedRoutes.contains(e) : Utils.toString("usedRoutes", usedRoutes, "e", e, "edgeIndexToUsedRoutes[edgeIndex]", edgeIndexToUsedRoutes[edgeIndex]);
routeIndexesRemove.add(e);
}
}
int routeIndexAdd = -1;
if (unusedRoutes.size() > 0) {
routeIndexAdd = unusedRoutes.get((int) (unusedRoutes.size() * rng.nextDouble()));
}

if (routeIndexesRemove.size() > 0) {
for (Integer routeIndexRemove : routeIndexesRemove) {
ArrayList<Node> nodesRemove = routeToNodes[routeIndexRemove.intValue()];
remove(routeIndexRemove.intValue(), nodesRemove);
}
}

ArrayList<Node> nodesAdd = null;
if (routeIndexAdd != -1) {
nodesAdd = search(routeIndexAdd);
if (nodesAdd != null) {
add(routeIndexAdd, nodesAdd);
}
}

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;
if (routeIndexesRemove.size() > 0) {
for (Integer routeIndexRemove : routeIndexesRemove) {
routeToNodes[routeIndexRemove.intValue()] = null;
}
}
if (routeIndexAdd != -1 && nodesAdd != null) {
routeToNodes[routeIndexAdd] = nodesAdd;
}
saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
if (routeIndexesRemove.size() > 0) {
for (Integer routeIndexRemove : routeIndexesRemove) {
add(routeIndexRemove.intValue(), routeToNodes[routeIndexRemove.intValue()]);
}
}
if (routeIndexAdd != -1 && nodesAdd != null) {
remove(routeIndexAdd, nodesAdd);
}
}

}

private void removeAndAddSameRoutesInAnEdge(int i) {

if (usedRoutes.size() == 0) {
return;
}

ArrayList<Integer> routeIndexes = new ArrayList<>();
{
int edgeIndex = (int) (edges.length * rng.nextDouble());
while (edgeIndexToUsedRoutes[edgeIndex].size() == 0) {
edgeIndex = (int) (edges.length * rng.nextDouble());
}
for (int j = 0; j < edgeIndexToUsedRoutes[edgeIndex].size(); j++) {
int e = edgeIndexToUsedRoutes[edgeIndex].get(j);
assert usedRoutes.contains(e) : Utils.toString("usedRoutes", usedRoutes, "e", e, "edgeIndexToUsedRoutes[edgeIndex]", edgeIndexToUsedRoutes[edgeIndex]);
routeIndexes.add(e);
}
assert routeIndexes.size() > 0;
}

Collections.shuffle(routeIndexes);

for (int j = 0; j < routeIndexes.size(); j++) {
int routeIndex = routeIndexes.get(j).intValue();
ArrayList<Node> nodesRemove = routeToNodes[routeIndex];
remove(routeIndex, nodesRemove);
}

ArrayList<Node>[] nodesAdd = new ArrayList[routeIndexes.size()];
for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
nodesAdd[j] = search(routeIndex);
if (nodesAdd[j] != null) {
add(routeIndex, nodesAdd[j]);
}
}

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;

for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
if (nodesAdd[j] != null) {
routeToNodes[routeIndex] = nodesAdd[j];
}
}

saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
if (nodesAdd[j] != null) {
remove(routeIndex, nodesAdd[j]);
}
}

for (int j = 0; j < routeIndexes.size(); j++) {
int routeIndex = routeIndexes.get(j).intValue();
ArrayList<Node> nodesRemove = routeToNodes[routeIndex];
add(routeIndex, nodesRemove);
}

}

}

private boolean[] isAvailable;

private void removeAndAddSubPath(int i) {

if (usedRoutes.size() == 0) {
return;
}

ArrayList<Integer> routeIndexes = new ArrayList<>();
int edgeIndex = (int) (edges.length * rng.nextDouble());
while (edgeIndexToUsedRoutes[edgeIndex].size() == 0) {
edgeIndex = (int) (edges.length * rng.nextDouble());
}
for (int j = 0; j < edgeIndexToUsedRoutes[edgeIndex].size(); j++) {
int e = edgeIndexToUsedRoutes[edgeIndex].get(j);
assert usedRoutes.contains(e) : Utils.toString("usedRoutes", usedRoutes, "e", e, "edgeIndexToUsedRoutes[edgeIndex]", edgeIndexToUsedRoutes[edgeIndex]);
routeIndexes.add(e);
}
assert routeIndexes.size() > 0;

isAvailable[edgeIndex] = false;

Collections.shuffle(routeIndexes);

for (int j = 0; j < routeIndexes.size(); j++) {
int routeIndex = routeIndexes.get(j).intValue();
ArrayList<Node> nodesRemove = routeToNodes[routeIndex];
remove(routeIndex, nodesRemove);
}

ArrayList<Node>[] nodesAdd = new ArrayList[routeIndexes.size()];
for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
nodesAdd[j] = search(routeIndex);
if (nodesAdd[j] != null) {
add(routeIndex, nodesAdd[j]);
}
}

isAvailable[edgeIndex] = true;

int deltaScore = calculateEdgeScorePlus() * calculateRouteScore() - score;
if (sa.accept(deltaScore)) {
this.score += deltaScore;

for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
if (nodesAdd[j] != null) {
routeToNodes[routeIndex] = nodesAdd[j];
}
}

saveBest();
countAC[i]++;
sumDeltaScore[i] += deltaScore;
} else {
for (int j = 0; j < nodesAdd.length; j++) {
int routeIndex = routeIndexes.get(j).intValue();
if (nodesAdd[j] != null) {
remove(routeIndex, nodesAdd[j]);
}
}

for (int j = 0; j < routeIndexes.size(); j++) {
int routeIndex = routeIndexes.get(j).intValue();
ArrayList<Node> nodesRemove = routeToNodes[routeIndex];
remove(routeIndex, nodesRemove);
}
for (int j = 0; j < routeIndexes.size(); j++) {
int routeIndex = routeIndexes.get(j).intValue();
ArrayList<Node> nodesRemove = routeToNodes[routeIndex];
add(routeIndex, nodesRemove);
}

}

}

private boolean check() {
HashSet<Integer> set = new HashSet<>();
for (int ei = 0; ei < edgeIndexToUsedRoutes.length; ei++) {
for (int i = 0; i < edgeIndexToUsedRoutes[ei].size(); i++) {
set.add(edgeIndexToUsedRoutes[ei].get(i));
}
}
HashSet<Integer> set2 = new HashSet<>();
for (int i = 0; i < usedRoutes.size(); i++) {
set2.add(usedRoutes.get(i));
}
return set2.containsAll(set) && set.containsAll(set2);
}

private void remove(int routeIndex, ArrayList<Node> nodes) {
unusedRoutes.add(routeIndex);
usedRoutes.removeValue(routeIndex);
for (Node node : nodes) {
edgeIndexToUsedRoutes[node.edgeIndex].removeValue(routeIndex);
}
}

private void add(int routeIndex, ArrayList<Node> nodes) {
unusedRoutes.removeValue(routeIndex);
usedRoutes.add(routeIndex);
for (Node node : nodes) {
edgeIndexToUsedRoutes[node.edgeIndex].add(routeIndex);
}
}

private PriorityQueue<Node> queue = new PriorityQueue<>();
private LinkedList<Node>[] queues = new LinkedList[1 << 7];
{
for (int i = 0; i < queues.length; i++) {
queues[i] = new LinkedList<>();
}
}
private int[] minDist;
private int[] maxPoints;

private ArrayList<Node> search2(int routeIndex) {
int inf = (int) 1e9;
queue.clear();
Arrays.fill(minDist, inf);
{
queue.add(new Node(null, routes[routeIndex].a, 0, inf, -1));
minDist[routes[routeIndex].a] = 0;
maxPoints[routes[routeIndex].a] = inf;
}
for (; !queue.isEmpty();) {
Node currentNode = queue.poll();

if (currentNode.currentCity == routes[routeIndex].b) {
return reverse(toList(currentNode));
}

if (currentNode.dist > minDist[currentNode.currentCity] || (currentNode.dist == minDist[currentNode.currentCity] && currentNode.points < maxPoints[currentNode.currentCity])) {
continue;
}

for (Edge2 edge2 : adjacentCities[currentNode.currentCity]) {
if (!isAvailable[edge2.edgeIndex]) {
continue;
}
if (edgeIndexToUsedRoutes[edge2.edgeIndex].size() > 0) {
if (currentNode.dist < minDist[edge2.to] || (currentNode.dist == minDist[edge2.to] && currentNode.points > maxPoints[edge2.to])) {
minDist[edge2.to] = currentNode.dist;
maxPoints[edge2.to] = currentNode.points;
queue.add(new Node(currentNode, edge2.to, currentNode.dist, currentNode.points, edge2.edgeIndex));
continue;
}
}
int nextDist = currentNode.dist + edge2.dist;
if (nextDist > numMaterials) {
continue;
}
int nextPoints = currentNode.points + edge2.points;
if (nextDist < minDist[edge2.to] || (nextDist == minDist[edge2.to] && nextPoints > maxPoints[edge2.to])) {
minDist[edge2.to] = nextDist;
maxPoints[edge2.to] = nextPoints;
queue.add(new Node(currentNode, edge2.to, nextDist, nextPoints, edge2.edgeIndex));
}
}
}
return null;
}

private ArrayList<Node> search(int routeIndex) {
int inf = (int) 1e9;
int distIndex = 0;
for (int i = 0; i < queues.length; i++) {
queues[i].clear();
}
Arrays.fill(minDist, inf);
{
queues[distIndex].add(new Node(null, routes[routeIndex].a, 0, inf, -1));
minDist[routes[routeIndex].a] = 0;
maxPoints[routes[routeIndex].a] = inf;
}

Node best = null;

A: for (;;) {
while (queues[distIndex].isEmpty()) {
distIndex++;
if (distIndex >= queues.length) {
break A;
}
}
Node currentNode = queues[distIndex].poll();

if (currentNode.dist > minDist[currentNode.currentCity] || (currentNode.dist == minDist[currentNode.currentCity] && currentNode.points < maxPoints[currentNode.currentCity])) {
continue;
}

if (currentNode.currentCity == routes[routeIndex].b) {
if (best == null || currentNode.dist < best.dist || (currentNode.dist == best.dist && currentNode.points > best.points)) {
best = currentNode;
}
}
if (best != null && distIndex > best.dist) {
break;
}

for (Edge2 edge2 : adjacentCities[currentNode.currentCity]) {
if (!isAvailable[edge2.edgeIndex]) {
continue;
}
if (edgeIndexToUsedRoutes[edge2.edgeIndex].size() > 0) {
if (currentNode.dist < minDist[edge2.to] || (currentNode.dist == minDist[edge2.to] && currentNode.points > maxPoints[edge2.to])) {
minDist[edge2.to] = currentNode.dist;
maxPoints[edge2.to] = currentNode.points;
queues[currentNode.dist].add(new Node(currentNode, edge2.to, currentNode.dist, currentNode.points, edge2.edgeIndex));
continue;
}
}
int nextDist = currentNode.dist + edge2.dist;
if (nextDist > numMaterials) {
continue;
}
int nextPoints = currentNode.points + edge2.points;
if (nextDist < minDist[edge2.to] || (nextDist == minDist[edge2.to] && nextPoints > maxPoints[edge2.to])) {
minDist[edge2.to] = nextDist;
maxPoints[edge2.to] = nextPoints;
queues[nextDist].add(new Node(currentNode, edge2.to, nextDist, nextPoints, edge2.edgeIndex));
}
}
}
return best == null ? null : reverse(toList(best));
}

private ArrayList<Node> search0(int routeIndex) {
PriorityQueue<Node> queue = new PriorityQueue<>();
boolean[] used2 = new boolean[numCities];
{
queue.add(new Node(null, routes[routeIndex].a, 0, 0, -1));
}
for (; !queue.isEmpty();) {
Node currentNode = queue.poll();

if (currentNode.currentCity == routes[routeIndex].b) {
return reverse(toList(currentNode));
}

if (used2[currentNode.currentCity]) {
continue;
}
used2[currentNode.currentCity] = true;

for (Edge2 edge2 : adjacentCities[currentNode.currentCity]) {
if (!isAvailable[edge2.edgeIndex]) {
continue;
}
if (edgeIndexToUsedRoutes[edge2.edgeIndex].size() > 0) {
if (!used2[edge2.to]) {
queue.add(new Node(currentNode, edge2.to, currentNode.dist, currentNode.points, edge2.edgeIndex));
continue;
}
}
if (currentNode.dist + edge2.dist > numMaterials) {
continue;
}
queue.add(new Node(currentNode, edge2.to, currentNode.dist + edge2.dist, currentNode.points + edge2.points, edge2.edgeIndex));
}
}
return null;
}

public static final ArrayList<Node> toList(Node state0) {
ArrayList<Node> list = new ArrayList<>();
for (Node state = state0; state.parent != null; state = state.parent) {
list.add(state);
}
return list;
}

public static final <T> ArrayList<T> reverse(ArrayList<T> list) {
for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
list.set(r, list.set(l, list.get(r)));
}
return list;
}

private int ei = 0;

private void flipEdge(int countIndex) {
--ei;
if (ei < 0) {
ei = remainderSolution.length - 1;
}

if (bestSolution[ei]) {
return;
}

remainderSolution[ei] = !remainderSolution[ei];

int deltaScore = (remainderSolution[ei] ? 1 : -1) * edges[ei].points * routeScore;
int deltaUsedMaterials = (remainderSolution[ei] ? 1 : -1) * edges[ei].dist;
if (this.usedMaterials + deltaUsedMaterials <= numMaterials && sa.accept(deltaScore)) {
this.score += deltaScore;
this.usedMaterials += deltaUsedMaterials;
this.edgeScore += (remainderSolution[ei] ? 1 : -1) * edges[ei].points;
remainderSaveBest();
} else {
remainderSolution[ei] = !remainderSolution[ei];
}
}

private void saveBest() {
if (score > bestScore) {
int usedMaterials2 = calculateUsedMaterials();
if (usedMaterials2 <= numMaterials) {
routeScore = calculateRouteScore();
edgeScore = calculateEdgeScore();
usedMaterials = usedMaterials2;
usedRoutesSize = usedRoutes.size();
bestScore = score;
for (int i = 0; i < edgeIndexToUsedRoutes.length; i++) {
bestSolution[i] = edgeIndexToUsedRoutes[i].size() > 0;
}
}
}
}

private void remainderSaveBest() {
if (score > bestScore) {
bestEdgeScore = edgeScore;
bestScore = score;
for (int i = 0; i < remainderSolution.length; i++) {
bestRemainderSolution[i] = bestSolution[i] || remainderSolution[i];
}
}
}

private void loadBest() {
}

private void remainderLoadBest() {
score = bestScore;
for (int i = 0; i < bestRemainderSolution.length; i++) {
bestSolution[i] = bestRemainderSolution[i];
}
}

private int[] makeSolution() {
int size = 0;
for (int i = 0; i < bestSolution.length; i++) {
if (bestSolution[i]) {
size++;
}
}

int[] res = new int[size];
for (int i = 0, j = 0; i < bestSolution.length; i++) {
if (bestSolution[i]) {
res[j++] = i;
}
}
return res;
}

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

int NumMaterials = Integer.parseInt(br.readLine());
int N = Integer.parseInt(br.readLine());
int E = Integer.parseInt(br.readLine());
String[] edges = new String[E];
for (int i = 0; i < E; i++)
edges[i] = br.readLine();
int R = Integer.parseInt(br.readLine());
String[] routes = new String[R];
for (int i = 0; i < R; i++)
routes[i] = br.readLine();

RoadNetwork rn = new RoadNetwork();
int[] ret = rn.findSolution(NumMaterials, N, E, edges, R, routes);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class Edge {
int a;
int b;
int dist;
int points;

public Edge(int a, int b, int dist, int points) {
super();
this.a = a;
this.b = b;
this.dist = dist;
this.points = points;
}
}

class Edge2 {
int edgeIndex;
int to;
int dist;
int points;

public Edge2(int edgeIndex, int to, int dist, int points) {
super();
this.edgeIndex = edgeIndex;
this.to = to;
this.dist = dist;
this.points = points;
}

}

class Route {
int a;
int b;
int points;

public Route(int a, int b, int points) {
super();
this.a = a;
this.b = b;
this.points = points;
}
}

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 double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

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

}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1 * 10 - 0.2;
public double time = startTime;

public double startTemperature = 1000;
public double endTemperature = 0.0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;

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

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

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;

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

update();
lastAcceptTemperature = inverseTemperature;
}

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

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

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

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

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

public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

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

if (deltaScore * inverseTemperature < -10) {
return false;
}

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

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

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

if (-deltaScore * inverseTemperature < -10) {
return false;
}

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

}

class Node implements Comparable<Node> {
Node parent;
int currentCity;
int dist;
int points;
int edgeIndex;

public Node(Node parent, int currentCity, int dist, int points, int edgeIndex) {
super();
this.parent = parent;
this.currentCity = currentCity;
this.dist = dist;
this.points = points;
this.edgeIndex = edgeIndex;
}

@Override
public int compareTo(Node o) {
if (dist < o.dist) {
return -1;
}
if (dist > o.dist) {
return 1;
}
if (points > o.points) {
return -1;
}
if (points < o.points) {
return 1;
}
return 0;
}

}

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;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
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 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() {
StringBuilder sb = new StringBuilder();
sb.append("{");
for (int i = 0; i < size; i++) {
sb.append(indexToValue[i]);
sb.append(i + 1 == size ? "" : ",");
}
sb.append("}");
return sb.toString();
}
}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}



Approach 無効な状態を許容する焼きなまし法です。

  • 近傍 : 1つマスを選んで、そのマスの数字を元の数字にもどす、または隣のセルの数字と同じ数字にする
    • 1つマスを選んで数字を±1する近傍で、探索空間が連結になるので、これでいいかなと思っていたら、上のの方が良かった。
  • ペナルティー : max(0,操作数 - M) の2乗
  • 数字が1のマスを収穫しない。




Approach 解説とほとんど同じです。

  • 今いる場所が不明箇所なら開ける
  • 最も近いペアを作る、または最も近い不明箇所を開ける
    • (最も近い不明箇所の距離 * 3.1 < 最も近いペアの距離 ? 不明箇所 : ペア) を選ぶ
    • 同じ距離なら中心に近い方を選ぶ
  • バタフライ効果が見られる。テストケース 50 個は少ない。




Approach ビームサーチです。

  • 各点の重み : (1 << 3 * 中心からのチェビシェフ距離)
    この後、対角線上の点なら 4 倍、その隣なら 2 倍する。
  • 評価関数 : 各点ごとに、合ってたら 1 ,違ってたら -1 を重みに掛けて和をとる。
    この評価関数は、外側からそろえる。
  • 次の深さのノードの作り方 : バウンディングボックスに完全に含まれるまわし方で、バウンディングボックスの端またはその一つ内側を含むものに限定
  • 重複除去に Zobrist hashing
    • 現在の深さのノード群を評価が良い順に見ていくときに除去する方法と、次の深さのノードを作るときに除去する方法が有ると思いますが、今回は前者を使いました。ハッシュセットを使わずに、評価とハッシュで並べ替えて、直前のノードと同じハッシュなら除去した。
  • ビーム幅 : 残り時間を275等分して、各深さごとできるだけ多くノードを見る。最初の方は1とか2で、最後の方は3桁くらい。
  • たまに完全解にならない

  • うまくいった時 208手(input_1.txt)



  • 時間制限10倍 うまくいった時 193手(input_1.txt)



  • 時間制限100倍 うまくいった時 174手(input_1.txt)




このページのトップヘ