EvbCFfp1XB

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



Approach 貪欲法+焼きなまし法です。

  • 貪欲法
    • 近いもの、必要なworkerの数が多いものを優先すると良かった。
    • 評価 : 移動時間 + 開始時間までの待ち時間 - 4 * 必要なworkerの数
    • 開始の時間はできるだけ早くした。
    • 暫定スコア :  597??
  • 焼きなまし法
    • 近傍 : あるworkerの仕事をランダムに選んで、他のworkerの最後の仕事にする
      • 仕事をランダムな位置に挿入する、交換する、2-optも試したが効果なし。
    • 暫定スコア : 貪欲法 + 100    ほとんど効果なし

source code

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

public class Main {
    private int n;
    private int[] x;
    private int[] y;
    private int[] d;
    private int[] p;
    private int[] l;
    private int[] h;
    private int[] duration;
    private int[] workers;
    private int[] start;
    private int[] completion;

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

    private double score;
    private double bestScore;

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        read();
        solve();
    }

    private void read() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            n = Integer.parseInt(br.readLine());
            x = new int[n];
            y = new int[n];
            d = new int[n];
            p = new int[n];
            l = new int[n];
            h = new int[n];
            for (int i = 0; i < n; i++) {
                String[] split = br.readLine().trim().split(" ");
                int j = 0;
                x[i] = Integer.parseInt(split[j++]);
                y[i] = Integer.parseInt(split[j++]);
                d[i] = Integer.parseInt(split[j++]);
                p[i] = Integer.parseInt(split[j++]);
                l[i] = Integer.parseInt(split[j++]);
                h[i] = Integer.parseInt(split[j++]);
            }
            duration = d;
            workers = p;
            start = new int[n];
            completion = new int[n];
            System.arraycopy(l, 0, start, 0, n);
            System.arraycopy(h, 0, completion, 0, n);
            countWorker = new int[n];
        } catch (NumberFormatException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private ArrayList> workerToJobs = new ArrayList<>();
    private int[] countWorker;

    private void solve() {
        greedy();
        SA();
        calculateScore2();

        for (ArrayList jobs : workerToJobs) {
            jobs.add(0, 0);
            jobs.add(0);
        }
        write(workerToJobs);
    }

    private void greedy() {

        for (;;) {

            if (!hasJob(countWorker)) {
                break;
            }

            int job = 0;
            int time = 0;
            ArrayList jobs = new ArrayList<>();

            for (;;) {

                double minDist = (int) 1e9;
                int minJob2 = -1;
                int minJob2Time = -1;
                for (int job2 = 1; job2 < n; job2++) {
                    if (job2 == job) {
                        continue;
                    }
                    if (countWorker[job2] >= workers[job2]) {
                        continue;
                    }
                    if (workers[job2] > 1) {
                    }

                    int time2 = time;
                    int dist = distance(job, job2);
                    time2 += dist;
                    int gap = Math.max(0, start[job2] - time2);
                    if (time2 < start[job2]) {
                        time2 = start[job2];
                    }
                    time2 += duration[job2];
                    if (time2 > completion[job2]) {
                        continue;
                    }

                    double k = dist + gap - 4 * workers[job2];
                    if (k < minDist) {
                        minDist = k;
                        minJob2 = job2;
                        minJob2Time = time2;
                    }
                }
                if (minJob2 == -1) {
                    break;
                }
                jobs.add(minJob2);
                job = minJob2;
                time = minJob2Time;
                if (countWorker[job]++ == 0) {
                    start[job] = time - duration[job];
                    completion[job] = time;
                }

            }
            workerToJobs.add(jobs);
        }

        score = calculateScore2();
        Utils.debug(score, score - scoreWorker - scoreDistance, scoreWorker, scoreDistance);
        Utils.debug("greedy", "score", score, "numWorkers", workerToJobs.size());
    }

    private boolean hasJob(int[] countWorker) {
        for (int job = 1; job < n; job++) {
            if (countWorker[job] < workers[job]) {
                return true;
            }
        }
        return false;
    }

    private boolean canEnd(int[] countWorker) {
        for (int job = 1; job < n; job++) {
            if (!(countWorker[job] <= 0 || countWorker[job] >= workers[job])) {
                return false;
            }
        }
        return true;
    }

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

                if (sa.isTLE()) {
                    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", (int) score), String.format("%d", (int) bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature, sa.lastAcceptIterations), sa.startTemperature, sa.endTemperature);
                    break;
                }
                if (watch.getSecond() > second) {
                    second++;
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%d", (int) score), String.format("%d", (int) bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature, sa.lastAcceptIterations), sa.startTemperature, sa.endTemperature);

                }
            }

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

    private void mutate() {
        removeAndAdd();
    }

    private void removeAndAdd() {
        if (workerToJobs.size() <= 1) {
            return;
        }

        int workerIndex = (int) (workerToJobs.size() * rng.nextDouble());
        int workerIndex2 = (int) (workerToJobs.size() * rng.nextDouble());
        while (workerIndex2 == workerIndex) {
            workerIndex2 = (int) (workerToJobs.size() * rng.nextDouble());
        }

        ArrayList jobs = workerToJobs.get(workerIndex);
        ArrayList jobs2 = workerToJobs.get(workerIndex2);

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

        int sumSize = jobs.size() + jobs2.size();

        int removeIndex = (int) (jobs.size() * rng.nextDouble());
        Integer remove2 = jobs.get(removeIndex);

        if (jobs2.contains(remove2)) {
            return;
        }
        jobs.remove(removeIndex);

        int addIndex = jobs2.size();
        jobs2.add(addIndex, remove2);

        double deltaScore = calculateScore2() - score;
        if (sa.accept(deltaScore)) {
            score += deltaScore;
            if (jobs.size() == 0) {
                workerToJobs.remove(workerIndex);
            }
        } else {
            jobs2.remove(addIndex);
            jobs.add(removeIndex, remove2);
        }
        assert jobs.size() + jobs2.size() == sumSize;
    }

    private int distance(int n, int n2) {
        return Math.abs(x[n] - x[n2]) + Math.abs(y[n] - y[n2]);
    }

    private int reward(int n) {
        return duration[n] * workers[n] * (workers[n] + 5);
    }

    private double calculateScore2() {
        bestScore = 0;
        scoreWorker = 0;
        scoreDistance = 0;
        System.arraycopy(l, 0, start, 0, n);
        System.arraycopy(h, 0, completion, 0, n);
        Arrays.fill(countWorker, 0);

        double score = 0;
        for (ArrayList jobs : workerToJobs) {
            double s = calculateScore2(jobs);
            score += s;
            bestScore = Math.max(bestScore, score);
        }
        return score;
    }

    private int scoreWorker = 0;
    private int scoreDistance = 0;

    private double calculateScore2(ArrayList jobs) {
        for (Integer job : jobs) {
            assert job.intValue() != 0;
        }

        int time = 0;
        int job = 0;
        double score = -240;
        scoreWorker += -240;
        for (int k = 0; k < jobs.size(); k++) {
            int njob = jobs.get(k).intValue();

            int distance = distance(job, njob);
            if (k == 0) {
                time = start[njob] - distance;
            }
            score -= distance;
            scoreDistance -= distance;
            time += distance;

            if (time < start[njob]) {
                score -= start[njob] - time;
                scoreDistance -= start[njob] - time;
                time = start[njob];
            }

            score -= duration[njob];
            scoreDistance -= duration[njob];
            time += duration[njob];

            if (time > completion[njob]) {
                score -= 1e5;
            }

            if (countWorker[njob]++ == 0) {
                score += reward(njob);
                start[njob] = time - duration[njob];
                completion[njob] = time;
            }

            job = njob;
        }
        int distance = distance(job, 0);
        score -= distance;
        scoreDistance -= distance;
        time += distance;

        return score;
    }

    private void write(ArrayList> workerToJobs) {
        Arrays.fill(countWorker, 0);
        this.score = 0;
        int i = 0;
        boolean afterBestScore = false;
        for (ArrayList jobs : workerToJobs) {
            if (afterBestScore) {
                if (canEnd(countWorker)) {
                    break;
                }
            }
            write2(jobs, countWorker);
            if (!afterBestScore) {
                if (Math.abs(this.score - bestScore) < 1e-5) {
                    afterBestScore = true;
                }
            }
        }
    }

    private void write2(ArrayList jobs, int[] countWorker) {
        int sumScore = 0;
        int score = 0;
        int time = 0;
        StringBuilder sb = new StringBuilder();
        for (int si = 0; si < jobs.size(); si++) {
            int i = (si) % jobs.size();
            int i2 = (si + 1) % jobs.size();
            int jobIndex = jobs.get(i).intValue();
            int jobIndex2 = jobs.get(i2).intValue();

            if (jobIndex == 0 && jobIndex2 == 0) {
                continue;
            }

            if (jobIndex == 0 && jobIndex2 != 0) {
                score = -240 * 1;
                time = this.start[jobIndex2] - distance(jobIndex, jobIndex2);
                sb.setLength(0);
                sb.append("start " + time + " 1\n");
            }

            score -= distance(jobIndex, jobIndex2) * 1;
            time += distance(jobIndex, jobIndex2);
            if (time < this.start[jobIndex2]) {
                score -= this.start[jobIndex2] - time;
                time = this.start[jobIndex2];
            }
            sb.append("arrive " + time + " " + (jobIndex2 + 1) + "\n");

            if (jobIndex2 != 0) {
                score -= duration[jobIndex2];
                time += duration[jobIndex2];
                sb.append("work " + (time - duration[jobIndex2]) + " " + time + " " + (jobIndex2 + 1) + "\n");
                if (time > completion[jobIndex2]) {
                    score += -1e7;
                }
                if (countWorker[jobIndex2] == 0) {
                    start[jobIndex2] = time - duration[jobIndex2];
                    completion[jobIndex2] = time;
                }
                countWorker[jobIndex2]++;
                if (countWorker[jobIndex2] == workers[jobIndex2]) {
                    score += reward(jobIndex2);
                }
            }

            if (jobIndex != 0 && jobIndex2 == 0) {
                {
                    sumScore += score;
                    this.score += score;
                    sb.append("end\n");
                    System.out.print(sb.toString());
                }
                time = 0;
            }

        }
    }

}

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 1 * 14.5;
    public double time = startTime;

    public double startTemperature = 1e1;
    public double endTemperature = 1e-9;
    public double expTemperature = 1;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

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

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

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;

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

        update();
        lastAcceptTemperature = inverseTemperature;
    }

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

    public void updateTemperature() {

        double time0to1 = elapsedPercentage(startTime, endTime, time);
        double temperature = interpolate(startTemperature, endTemperature, time0to1);

        inverseTemperature = 1.0 / temperature;
    }

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

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

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

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

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

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

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

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

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

        if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

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

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

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

        if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

}

final class Utils {
    private Utils() {
    }

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

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

}

class Watch {
    private long start;

    public Watch() {
        init();
    }

    public double getSecond() {
        return (System.nanoTime() - start) * 1e-9;
    }

    public void init() {
        init(System.nanoTime());
    }

    private void init(long start) {
        this.start = start;
    }

    public String getSecondString() {
        return toString(getSecond());
    }

    public static final String toString(double second) {
        if (second < 60) {
            return String.format("%5.2fs", second);
        } else if (second < 60 * 60) {
            int minute = (int) (second / 60);
            return String.format("%2dm%2ds", minute, (int) (second % 60));
        } else {
            int hour = (int) (second / (60 * 60));
            int minute = (int) (second / 60);
            return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
        }
    }

}

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

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

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

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

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

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

}




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のマスを収穫しない。


このページのトップヘ