README.md

日本橋大渋滞 テスター

• これは RCO presents 日本橋ハーフマラソン 本戦 の 問題B - 日本橋大渋滞 のテストケースジェネレータとジャッジのためのプログラムです。これらを用いることで、ローカル環境でプログラムのテストを行うことができます。
• これらのプログラム上で計算された得点は、当コンテストでの得点ではありません。また、これらのプログラム上で計算された得点は、当コンテストでの得点を保証するものではありません。
• これらのプログラムを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
• これらのプログラムに関する質問は受け付けていません。予めご了承ください。
• これらのプログラムの一部を、コンテストの解答に流用してもかまいません。

コンパイル

Generator.java, Judge.java, TestCase.java の 3 つのファイルを同じディレクトリに設置し、以下のコマンドを実行してください。

javac Generator.java
javac Judge.java

テストケース生成

コンパイル後、好きな乱数シードを整数で与えることで、問題文の条件を満たすテストケースを生成できます。以下のコマンドでは 123 という値を乱数シード値として、input.txt というテキストファイルにテストケースを保存しています。

java Generator -seed 123 > input.txt

得点計算

コンパイル後、テストケースのテキストファイルと、自分のプログラムの出力結果のテキストファイルから、テストケースに対する得点を計算することができます。以下のコマンドでは、 input.txt というテキストファイルに保存されたテストケースに対する output.txt というテキストファイル内の出力から得られる得点を計算しています。

java Judge input.txt output.txt

Generator.java

import java.util.Random;

public class Generator {

    public static void main(String[] args) throws Exception {
        long seed = new Random().nextInt();
        for (int i = 0; i < args.length; ++i) {
            if (args[i].equals("-seed")) {
                seed = Long.parseLong(args[++i]);
            }
        }
        TestCase testcase = new TestCase(seed);
        System.out.println(testcase);
    }

}

Judge.java

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Scanner;

public class Judge {

    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, 1, 0, -1};

    static class Result {
        TestCase input;
        double score;
        double penaTime;
        double penaDist;

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("P_D:" + penaDist + "\n");
            builder.append("P_T:" + penaTime + "\n");
            builder.append("score:" + (int)Math.ceil(score) + "\n");
            return builder.toString();
        }
    }

    static class Output {
        char[][] move;

        Output(Scanner sc) {
            int C = sc.nextInt();
            this.move = new char[C][];
            for (int i = 0; i < C; i++) {
                this.move[i] = sc.next().toCharArray();
            }
        }
    }

    static Result calcScore(TestCase testcase, Output output) {
        final int EMPTY = -1;
        final int RESERVED = -2;
        Result res = new Result();
        res.input = testcase;
        int L = output.move.length;
        if (L > testcase.T) {
            throw new RuntimeException("move count " + L + " is larger than T.");
        }
        int[][] car = new int[testcase.H][testcase.W];
        for (int[] a : car) {
            Arrays.fill(a, EMPTY);
        }
        for (int i = 0; i < testcase.K; i++) {
            int r = testcase.A[i] - 1;
            int c = testcase.B[i] - 1;
            car[r][c] = i;
        }
        for (int i = 0; i < L; i++) {
            if (output.move[i].length != testcase.K) {
                throw new RuntimeException("command length does not equal to K at time " + i + ".");
            }
            for (int r = 0; r < testcase.H; r++) {
                for (int c = 0; c < testcase.W; c++) {
                    if (car[r][c] == EMPTY || car[r][c] == RESERVED) continue;
                    char command = output.move[i][car[r][c]];
                    if (command == '-') continue;
                    int dir = "URDL".indexOf(command);
                    if (dir < 0) {
                        throw new RuntimeException("command " + command + " is not valid at time " + i + " car " + (car[r][c] + 1) + ".");
                    }
                    int nr = r + DR[dir];
                    int nc = c + DC[dir];
                    if (nr < 0 || testcase.H <= nr || nc < 0 || testcase.W <= nc) {
                        throw new RuntimeException("invalid direction " + command + " at time " + i + " car " + (car[r][c] + 1) + ".");
                    }
                    if (car[nr][nc] == EMPTY) {
                        car[nr][nc] = RESERVED;
                    } else if (car[nr][nc] == RESERVED) {
                        throw new RuntimeException("multiple cars are moving to the same position at time " + i + ".");
                    } else {
                        throw new RuntimeException("car " + (car[r][c] + 1) + " is moving to the position another car exists at time " + i + ".");
                    }
                }
            }
            boolean[] moved = new boolean[testcase.K];
            for (int r = 0; r < testcase.H; r++) {
                for (int c = 0; c < testcase.W; c++) {
                    if (car[r][c] == EMPTY || car[r][c] == RESERVED) continue;
                    int carId = car[r][c];
                    if (moved[carId]) continue;
                    char command = output.move[i][carId];
                    if (command == '-') continue;
                    int dir = "URDL".indexOf(command);
                    int nr = r + DR[dir];
                    int nc = c + DC[dir];
                    car[nr][nc] = carId;
                    car[r][c] = EMPTY;
                    moved[carId] = true;
                }
            }
        }
        res.penaDist = 20;
        for (int r = 0; r < testcase.H; r++) {
            for (int c = 0; c < testcase.W; c++) {
                if (car[r][c] == EMPTY) continue;
                int carIdx = car[r][c];
                int dstR = testcase.C[carIdx] - 1;
                int dstC = testcase.D[carIdx] - 1;
                int dist = Math.abs(dstC - c) + Math.abs(dstR - r);
                res.penaDist += dist;
            }
        }
        res.penaTime = 10 + 0.01 * output.move.length;
        res.score = 10_000_000.0 / (res.penaDist * res.penaTime);
        return res;
    }

    public static void main(String[] args) throws Exception {
        if (args.length < 2) {
            System.err.println("usage: java Judge input_file_path output_file_path");
            System.exit(1);
        }
        Path inputFile = Paths.get(args[0]);
        Path outputFile = Paths.get(args[1]);
        TestCase testcase = new TestCase(new Scanner(inputFile));
        Output output = new Output(new Scanner(outputFile));
        Result res = calcScore(testcase, output);
        System.out.print(res);
    }

}

TestCase.java

import java.security.SecureRandom;
import java.util.Scanner;

public class TestCase {

    static final int MIN_SIZE = 30;
    static final int MAX_SIZE = 30;
    static final int MIN_T = 10000;
    static final int MAX_T = 10000;
    static final double MIN_RATIO_K = 0.5;
    static final double MAX_RATIO_K = 0.5;

    SecureRandom rnd;
    int H, W, K, T;
    int[] A, B, C, D;

    TestCase(long seed) throws Exception {
        rnd = SecureRandom.getInstance("SHA1PRNG");
        rnd.setSeed(seed);
        this.H = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
        this.W = rnd.nextInt(MAX_SIZE - MIN_SIZE + 1) + MIN_SIZE;
        double ratioK = rnd.nextDouble() * (MAX_RATIO_K - MIN_RATIO_K) + MIN_RATIO_K;
        this.K = (int) Math.ceil(this.H * this.W * ratioK);
        this.T = rnd.nextInt(MAX_T - MIN_T + 1) + MIN_T;
        this.A = new int[K];
        this.B = new int[K];
        this.C = new int[K];
        this.D = new int[K];
        int[] pos = new int[H * W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                pos[i * W + j] = (i << 16) | j;
            }
        }
        shuffle(pos);
        for (int i = 0; i < K; i++) {
            this.A[i] = (pos[i] & 0xFFFF) + 1;
            this.B[i] = (pos[i] >> 16) + 1;
        }
        shuffle(pos);
        for (int i = 0; i < K; i++) {
            this.C[i] = (pos[i] & 0xFFFF) + 1;
            this.D[i] = (pos[i] >> 16) + 1;
        }
    }

    private void shuffle(int[] ar) {
        for (int i = 0; i < ar.length; i++) {
            int to = rnd.nextInt(ar.length - i) + i;
            int tmp = ar[i];
            ar[i] = ar[to];
            ar[to] = tmp;
        }
    }

    TestCase(Scanner sc) throws Exception {
        this.H = sc.nextInt();
        this.W = sc.nextInt();
        this.K = sc.nextInt();
        this.T = sc.nextInt();
        this.A = new int[K];
        this.B = new int[K];
        this.C = new int[K];
        this.D = new int[K];
        for (int i = 0; i < this.K; i++) {
            this.A[i] = sc.nextInt();
            this.B[i] = sc.nextInt();
            this.C[i] = sc.nextInt();
            this.D[i] = sc.nextInt();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(this.H + " " + this.W + " " + this.K + " " + this.T + "\n");
        for (int i = 0; i < K; ++i) {
            builder.append(this.A[i] + " " + this.B[i] + " " + this.C[i] + " " + this.D[i] + "\n");
        }
        return builder.toString();
    }

}