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

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

}