RCO presents 日本橋ハーフマラソン 本戦

Submission #1174208

Source codeソースコード

import java.util.*;

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

    private static final int[] dx = {1, 0, -1, 0};
    private static final int[] dy = {0, 1, 0, -1};
    private static final String[] ds = {"L", "U", "R", "D"};
    private Main.XorShift random = new Main.XorShift();
    int h, w, k, t;
    int[] cars, goal;

    String dir(int a, int b, int c, int d) {
        int ac = a - c;
        int bd = b - d;
        if (ac == 0 && bd == 0) return "-";
        for (int i = 0; i < 4; ++i) {
            if (ac == dy[i] && bd == dx[i]) return ds[i];
        }
        throw new RuntimeException(ac + " " + bd);
    }

    void solve() {
        try (Scanner in = new Scanner(System.in)) {
            h = in.nextInt();
            w = in.nextInt();
            k = in.nextInt();
            t = in.nextInt();
            long start = System.currentTimeMillis();
            cars = new int[k * 2];
            goal = new int[k * 2];
            for (int i = 0; i < k; ++i) {
                cars[i * 2 + 0] = in.nextInt() - 1;
                cars[i * 2 + 1] = in.nextInt() - 1;
                goal[i * 2 + 0] = in.nextInt() - 1;
                goal[i * 2 + 1] = in.nextInt() - 1;
            }
            PriorityQueue<State> queue[] = new PriorityQueue[t];
            for (int i = 0; i < t; ++i) queue[i] = new PriorityQueue<>();
            State best = new State(null, cars, 0);
            int L = 0;
            queue[0].add(best);
            boolean used[] = new boolean[h * w + 1];
            int NE[] = new int[10];
            int value[] = new int[5];
            int C = h / 2;
            int selectSort[][] = new int[k][2];
            long time = 0;
            end:
            while (true) {
                for (int i = 0; i < t / 10; ++i) {
                    if (i % 100 == 0) {
                        time = System.currentTimeMillis() - start;
                        if (time > 3700) break end;
                    }
                    State now = queue[i].poll();
                    if (now == null) continue;
                    if (best.score < now.score) {
                        best = now;
                        L = i;
                    }
                    for (int j = 0; j < k; ++j) {
                        selectSort[j][0] = j;
                        selectSort[j][1] = dist(now.cars[j * 2], now.cars[j * 2 + 1], goal[j * 2], goal[j * 2 + 1]);
                    }
                    Arrays.sort(selectSort, (a, b) -> b[1] - a[1]);
                    boolean fin = time > 3300;
                    for (int j = 0; j < 5; ++j) {
                        int next[] = Arrays.copyOf(now.cars, now.cars.length);
                        Arrays.fill(used, false);
                        for (int x = 0; x < k; ++x) {
                            used[next[x * 2] * h + next[x * 2 + 1]] = true;
                        }
                        for (int si = 0; si < k; ++si) {
                            int x = selectSort[si][0];
                            int a = next[x * 2];
                            int b = next[x * 2 + 1];
                            int c = 1;
                            NE[0] = a;
                            NE[1] = b;
                            int goalDist = dist(a, b, goal[x * 2], goal[x * 2 + 1]);
                            value[0] = 1 + (goalDist == 0 ? 5 : 0);
                            if (fin && goalDist == 0) {
                            } else {
                                for (int z = 0; z < 4; ++z) {
                                    int na = a + dy[z];
                                    int nb = b + dx[z];
                                    if (!in(na, nb) || used[na * h + nb]) continue;
                                    boolean up = goalDist > dist(na, nb, goal[x * 2], goal[x * 2 + 1]);
                                    boolean center = dist(a, b, C, C) > dist(na, nb, C, C);
                                    NE[c * 2 + 0] = na;
                                    NE[c * 2 + 1] = nb;
                                    value[c] = 1 + (up ? 10 : 0) + (center ? 0 : 2);
                                    ++c;
                                }
                            }
                            int v = random(NE, c, value);
                            next[x * 2] = NE[v * 2];
                            next[x * 2 + 1] = NE[v * 2 + 1];
                            used[next[x * 2] * h + next[x * 2 + 1]] = true;
                        }
                        queue[i + 1].add(new State(now, next, i));
                    }
                }
            }

            List<String> move = new ArrayList<>();
            while (best.prev != null) {
                StringBuilder m = new StringBuilder();
                int[] nc = best.cars;
                int[] pc = best.prev.cars;
                for (int i = 0; i < k; ++i) {
                    m.append(dir(pc[i * 2], pc[i * 2 + 1], nc[i * 2], nc[i * 2 + 1]));
                }
                m.append("\n");
                move.add(m.toString());
                best = best.prev;
            }
            Collections.reverse(move);
            StringBuilder res = new StringBuilder();
            res.append(L).append("\n");
            for (String s : move) res.append(s);
            System.out.println(res);
        }
    }

    int random(int ne[], int c, int value[]) {
        int sum = 0;
        for (int i = 0; i < c; ++i) {
            sum += value[i];
        }
        int x = random.nextInt(sum);
        for (int i = 0; i < c; ++i) {
            if (x < value[i])
                return i;
            x -= value[i];
        }
        throw new RuntimeException();
    }

    boolean in(int a, int b) {
        return 0 <= a && a < h && 0 <= b && b < w;
    }

    class State implements Comparable<State> {
        State prev;
        int cars[];
        double score;

        State(State prev, int[] cars, int L) {
            this.prev = prev;
            this.cars = cars;
            this.score = score(cars, goal, L);
        }

        @Override
        public int compareTo(State o) {
            return Double.compare(o.score, score);
        }
    }

    int dist(int a, int b, int c, int d) {
        return Math.abs(a - c) + Math.abs(b - d);
    }

    double score(int[] cars, int[] goal, int L) {
        int pd = 20;
        for (int i = 0; i < k; ++i) {
            pd += dist(cars[i * 2], cars[i * 2 + 1], goal[i * 2], goal[i * 2 + 1]);
        }
        double pt = 10.0 + L * 0.01;
        return 10000000.0 / (pd * pt);
    }

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

        int nextInt(int n) {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = (w ^ (w >>> 19)) ^ (t ^ (t >>> 8));
            final int r = w % n;
            return r < 0 ? r + n : r;
        }

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

        long nextLong() {
            return ((long) nextInt() << 32) | (long) nextInt();
        }
    }

    private void tr(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}

Submission

Task問題 B - 日本橋大渋滞
User nameユーザ名 hoshi524
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 350560
Source lengthソースコード長 7633 Byte
File nameファイル名
Exec time実行時間 3905 ms
Memory usageメモリ使用量 382012 KB

Compiler messageコンパイルメッセージ

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Test case

Set

Set name Score得点 / Max score Cases
test_01 17212 / 50000 subtask_01_01.txt
test_02 10465 / 50000 subtask_01_02.txt
test_03 13072 / 50000 subtask_01_03.txt
test_04 4972 / 50000 subtask_01_04.txt
test_05 20022 / 50000 subtask_01_05.txt
test_06 17254 / 50000 subtask_01_06.txt
test_07 6847 / 50000 subtask_01_07.txt
test_08 4262 / 50000 subtask_01_08.txt
test_09 8457 / 50000 subtask_01_09.txt
test_10 4655 / 50000 subtask_01_10.txt
test_11 10823 / 50000 subtask_01_11.txt
test_12 8795 / 50000 subtask_01_12.txt
test_13 15048 / 50000 subtask_01_13.txt
test_14 7906 / 50000 subtask_01_14.txt
test_15 19285 / 50000 subtask_01_15.txt
test_16 7971 / 50000 subtask_01_16.txt
test_17 22995 / 50000 subtask_01_17.txt
test_18 14855 / 50000 subtask_01_18.txt
test_19 15883 / 50000 subtask_01_19.txt
test_20 7198 / 50000 subtask_01_20.txt
test_21 10732 / 50000 subtask_01_21.txt
test_22 4285 / 50000 subtask_01_22.txt
test_23 12765 / 50000 subtask_01_23.txt
test_24 5543 / 50000 subtask_01_24.txt
test_25 5144 / 50000 subtask_01_25.txt
test_26 11417 / 50000 subtask_01_26.txt
test_27 17374 / 50000 subtask_01_27.txt
test_28 4099 / 50000 subtask_01_28.txt
test_29 25028 / 50000 subtask_01_29.txt
test_30 16196 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 3852 ms 281468 KB
subtask_01_02.txt AC 3823 ms 341220 KB
subtask_01_03.txt AC 3846 ms 376132 KB
subtask_01_04.txt AC 3835 ms 338308 KB
subtask_01_05.txt AC 3858 ms 308896 KB
subtask_01_06.txt AC 3862 ms 338096 KB
subtask_01_07.txt AC 3840 ms 379224 KB
subtask_01_08.txt AC 3840 ms 274544 KB
subtask_01_09.txt AC 3842 ms 277792 KB
subtask_01_10.txt AC 3860 ms 227696 KB
subtask_01_11.txt AC 3852 ms 278880 KB
subtask_01_12.txt AC 3843 ms 290580 KB
subtask_01_13.txt AC 3877 ms 284428 KB
subtask_01_14.txt AC 3855 ms 375088 KB
subtask_01_15.txt AC 3856 ms 293960 KB
subtask_01_16.txt AC 3831 ms 308244 KB
subtask_01_17.txt AC 3852 ms 324020 KB
subtask_01_18.txt AC 3845 ms 280492 KB
subtask_01_19.txt AC 3858 ms 375772 KB
subtask_01_20.txt AC 3837 ms 333464 KB
subtask_01_21.txt AC 3905 ms 382012 KB
subtask_01_22.txt AC 3841 ms 299412 KB
subtask_01_23.txt AC 3840 ms 300968 KB
subtask_01_24.txt AC 3861 ms 285508 KB
subtask_01_25.txt AC 3866 ms 314508 KB
subtask_01_26.txt AC 3896 ms 349484 KB
subtask_01_27.txt AC 3841 ms 328736 KB
subtask_01_28.txt AC 3844 ms 336440 KB
subtask_01_29.txt AC 3878 ms 345320 KB
subtask_01_30.txt AC 3887 ms 297272 KB