EvbCFfp1XB

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


問題

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

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


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

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



source code(Solver IP)





source code(Solver SA)





source code(Tester)




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

↑このページのトップヘ