EvbCFfp1XB

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

May 2019


問題

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

}


↑このページのトップヘ