RCO presents 日本橋ハーフマラソン 本戦 (オープン)

Submission #1174379

Source codeソースコード

import java.util.ArrayList;
import java.util.Scanner;
import java.util.SplittableRandom;
 
public class Main {
 
    static long startTime = System.currentTimeMillis();
    static final int TL = 3990;
    static final int[] DR = new int[]{1, 0, -1, 0, 0};
    static final int[] DC = new int[]{0, 1, 0, -1, 0};
    static final char[] DIR_CHARS = "DRUL-".toCharArray();
    static Scanner sc = new Scanner(System.in);
    static SplittableRandom rnd = new SplittableRandom(42);
    static int H, W, K, T;
    static int[][] carPos, origCarPos, convergePos;
    static char[][] moves;
    static int[] order;
    static int time;
    static int sumDist;
    static int[][] used;
    static int usedIdx;
 
    public static void main(String[] args) {
        H = sc.nextInt();
        W = sc.nextInt();
        K = sc.nextInt();
        T = sc.nextInt();
        carPos = new int[4][K];
        origCarPos = new int[4][K];
        convergePos = new int[4][K];
        order = new int[K];
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 4; j++) {
                origCarPos[j][i] = sc.nextInt() - 1;
            }
            order[i] = i;
        }
        moves = new char[T][K];
        used = new int[H][W];
        ArrayList<String> ans = new ArrayList<>();
        double ansScore = 0;
 
        long worstTime = 0;
        for (int turn = 0; ; turn++) {
            long beforeTime = System.currentTimeMillis() - startTime;
            if (beforeTime + worstTime > TL) {
                System.err.println("turn:" + turn);
                break;
            }
            for (int i = 0; i < 4; i++) {
                System.arraycopy(origCarPos[i], 0, carPos[i], 0, K);
            }
            sumDist = 0;
            for (int i = 0; i < K; i++) {
                sumDist += Math.abs(carPos[0][i] - carPos[2][i]) + Math.abs(carPos[1][i] - carPos[3][i]);
            }
 
            int bestTime = 0;
            double bestScore = calcScore(sumDist, 0);
            for (time = 1; time <= T; time++) {
                boolean update = move();
                if (!update) break;
                double score = calcScore(sumDist, time);
                if (score > bestScore) {
                    bestScore = score;
                    bestTime = time;
                }
                if (calcScore(0, time) < ansScore) {
                    System.err.println("time:" + time);
                    break;
                }
            }
            System.err.println("bestScore:" + bestScore);
            if (bestScore > ansScore) {
                ansScore = bestScore;
                ans.clear();
                for (int i = 0; i < bestTime; i++) {
                    ans.add(String.valueOf(moves[i]));
                }
            }
 
            worstTime = Math.max(worstTime, System.currentTimeMillis() - startTime - beforeTime);
        }
        System.out.println(ans.size());
        for (String s : ans) {
            System.out.println(s);
        }
    }
 
    static boolean move() {
        usedIdx++;
        for (int i = 0; i < K; i++) {
            int pos = rnd.nextInt(K - i) + i;
            int tmp = order[i];
            order[i] = order[pos];
            order[pos] = tmp;
            used[carPos[0][i]][carPos[1][i]] = usedIdx;
        }
        ArrayList<Integer> nearList = new ArrayList<>();
        ArrayList<Integer> farList = new ArrayList<>();
        int stayFactor;
        if (sumDist < 100) {
            stayFactor = 99;
        } else if (sumDist < 200) {
            stayFactor = 4;
        } else if (sumDist < 300) {
            stayFactor = 2;
        } else if (sumDist < 500) {
            stayFactor = 2;
        } else if (sumDist < 1000) {
            stayFactor = 1;
        } else {
            stayFactor = 0;
        }
 
        sumDist = 0;
        boolean update = false;
        for (int i = 0; i < K; i++) {
            nearList.clear();
            farList.clear();
            int ci = order[i];
            int dist = Math.abs(carPos[1][ci] - carPos[3][ci]) + Math.abs(carPos[0][ci] - carPos[2][ci]);
            for (int j = 0; j < 4; j++) {
                int nr = carPos[0][ci] + DR[j];
                int nc = carPos[1][ci] + DC[j];
                if (nr < 0 || H <= nr || nc < 0 || W <= nc) continue;
                if (used[nr][nc] == usedIdx) continue;
                int nDist = Math.abs(nr - carPos[2][ci]) + Math.abs(nc - carPos[3][ci]);
                if (dist > nDist) {
                    nearList.add(j);
                } else {
                    farList.add(j);
                }
            }
            int dir;
            if (dist == 0 && stayFactor == 99) {
                dir = 4;
            } else if (nearList.size() == 1) {
                dir = nearList.get(0);
                --dist;
            } else if (nearList.size() == 2) {
                int nr0 = carPos[0][ci] + DR[nearList.get(0)];
                int nc0 = carPos[1][ci] + DC[nearList.get(0)];
                int distFromEdge0 = distFromEdge(nr0, nc0);
                int nr1 = carPos[0][ci] + DR[nearList.get(1)];
                int nc1 = carPos[1][ci] + DC[nearList.get(1)];
                int distFromEdge1 = distFromEdge(nr1, nc1);
                if (distFromEdge0 < distFromEdge1) {
                    nearList.add(nearList.get(0));
                } else if (distFromEdge0 > distFromEdge1) {
                    nearList.add(nearList.get(1));
                }
                dir = nearList.get(rnd.nextInt(nearList.size()));
                --dist;
            } else if (!farList.isEmpty()) {
                if (stayFactor == 0 && farList.size() >= 2) {
                    int nr0 = carPos[0][ci] + DR[farList.get(0)];
                    int nc0 = carPos[1][ci] + DC[farList.get(0)];
                    int distFromEdge0 = distFromEdge(nr0, nc0);
                    int nr1 = carPos[0][ci] + DR[farList.get(1)];
                    int nc1 = carPos[1][ci] + DC[farList.get(1)];
                    int distFromEdge1 = distFromEdge(nr1, nc1);
                    if (distFromEdge0 < distFromEdge1) {
                        farList.add(farList.get(0));
                    } else if (distFromEdge0 > distFromEdge1) {
                        farList.add(farList.get(1));
                    }
                }
                for (int j = 0; j < stayFactor; j++) {
                    farList.add(4);
                }
                dir = farList.get(rnd.nextInt(farList.size()));
                if (dir != 4) dist++;
            } else {
                dir = 4;
            }
            moves[time - 1][ci] = DIR_CHARS[dir];
            carPos[0][ci] += DR[dir];
            carPos[1][ci] += DC[dir];
            used[carPos[0][ci]][carPos[1][ci]] = usedIdx;
            sumDist += dist;
            if (dir != 4) update = true;
        }
        return update;
    }
 
    static int distFromEdge(int r, int c) {
        return Math.min(Math.min(r, H - 1 - r), Math.min(c, W - 1 - c));
    }
 
    static double calcScore(int dist, int time) {
        double distFactor = 20 + dist;
        double timeFactor = 10 + 0.01 * time;
        return 10_000_000.0 / (distFactor * timeFactor);
    }
}

Submission

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

Test case

Set

Set name Score得点 / Max score Cases
test_01 29326 / 50000 subtask_01_01.txt
test_02 30322 / 50000 subtask_01_02.txt
test_03 29121 / 50000 subtask_01_03.txt
test_04 27825 / 50000 subtask_01_04.txt
test_05 25044 / 50000 subtask_01_05.txt
test_06 26667 / 50000 subtask_01_06.txt
test_07 23497 / 50000 subtask_01_07.txt
test_08 29482 / 50000 subtask_01_08.txt
test_09 24202 / 50000 subtask_01_09.txt
test_10 24962 / 50000 subtask_01_10.txt
test_11 26897 / 50000 subtask_01_11.txt
test_12 25240 / 50000 subtask_01_12.txt
test_13 25051 / 50000 subtask_01_13.txt
test_14 26169 / 50000 subtask_01_14.txt
test_15 24571 / 50000 subtask_01_15.txt
test_16 27825 / 50000 subtask_01_16.txt
test_17 25988 / 50000 subtask_01_17.txt
test_18 27145 / 50000 subtask_01_18.txt
test_19 24814 / 50000 subtask_01_19.txt
test_20 25721 / 50000 subtask_01_20.txt
test_21 28043 / 50000 subtask_01_21.txt
test_22 28297 / 50000 subtask_01_22.txt
test_23 27732 / 50000 subtask_01_23.txt
test_24 24438 / 50000 subtask_01_24.txt
test_25 25760 / 50000 subtask_01_25.txt
test_26 29586 / 50000 subtask_01_26.txt
test_27 26414 / 50000 subtask_01_27.txt
test_28 25563 / 50000 subtask_01_28.txt
test_29 25155 / 50000 subtask_01_29.txt
test_30 29604 / 50000 subtask_01_30.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 3714 ms 57060 KB
subtask_01_02.txt AC 3878 ms 55436 KB
subtask_01_03.txt AC 3712 ms 55296 KB
subtask_01_04.txt AC 3661 ms 54000 KB
subtask_01_05.txt AC 3723 ms 58112 KB
subtask_01_06.txt AC 3780 ms 55472 KB
subtask_01_07.txt AC 3765 ms 54656 KB
subtask_01_08.txt AC 3758 ms 57388 KB
subtask_01_09.txt AC 3769 ms 55956 KB
subtask_01_10.txt AC 3820 ms 57796 KB
subtask_01_11.txt AC 3677 ms 55332 KB
subtask_01_12.txt AC 3428 ms 54780 KB
subtask_01_13.txt AC 3538 ms 55536 KB
subtask_01_14.txt AC 3821 ms 57332 KB
subtask_01_15.txt AC 3672 ms 53312 KB
subtask_01_16.txt AC 3886 ms 55884 KB
subtask_01_17.txt AC 3813 ms 53200 KB
subtask_01_18.txt AC 3826 ms 54904 KB
subtask_01_19.txt AC 3793 ms 57436 KB
subtask_01_20.txt AC 3777 ms 58364 KB
subtask_01_21.txt AC 3799 ms 57824 KB
subtask_01_22.txt AC 3891 ms 52980 KB
subtask_01_23.txt AC 3828 ms 55840 KB
subtask_01_24.txt AC 3861 ms 57952 KB
subtask_01_25.txt AC 3757 ms 57684 KB
subtask_01_26.txt AC 3745 ms 60120 KB
subtask_01_27.txt AC 3849 ms 57560 KB
subtask_01_28.txt AC 3792 ms 56756 KB
subtask_01_29.txt AC 3853 ms 55532 KB
subtask_01_30.txt AC 3865 ms 55832 KB