山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 024

問題

Tasks - AtCoder Beginner Contest 024

C問題は解くことができなかったので解説を見ました。Beginnerとはいったい・・・。まあ、やさしい理系数学という本もあるくらいだしね。

A - 動物園

A問題なのに入力が多いです。算数の問題ですな。

B - 自動ドア

B問題なのに部分点がある問題です。

解き方は複数あると思いますが、僕は時刻tex[A_i] の差分が T より大きいかどうかで解答を作りました。ここで、その差分を

 B_i = A_i - A_{i ^ 1}

とします。 B_i T を超えていた場合、次の客が来るまで自動ドアが閉じているので、求める時間に T を加算します。一方で、 B_i T以下である場合、次の客が来るまでドアが開いているので、 B_i を加算します。

最後の客が到着してから自動ドアは T の間開くことになるので、これも加算します。

コード
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int T = scan.nextInt();
        int []A = new int[N];
        for(int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        scan.close();
        int sum = T;

        int []B = new int[N - 1];
        for(int i = 0; i < N - 1; i++) {
            B[i] = A[i+1] - A[i];
        }
        for(int i = 0; i < N - 1; i++) {
            if(B[i] > T) {
                sum += T;
            }else {
                sum += B[i];
            }
        }
        System.out.println(sum);
    }
}

C - 民族大移動

解説の図のようなことは考えついたんですが、実装までには至りませんでした。

コード
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int D = scan.nextInt();
        int K = scan.nextInt();
        int[]L = new int[D];
        int[]R = new int[D];
        int[]S = new int[K];
        int[]T = new int[K];
        for(int i = 0; i < D; i++) {
            L[i] = scan.nextInt();
            R[i] = scan.nextInt();
        }
        for(int i = 0; i < K; i++) {
            S[i] = scan.nextInt();
            T[i] = scan.nextInt();
        }
        scan.close();
        int[]d = new int[K];
        for(int i = 0; i < K; i++) {
            int t = S[i];
            for(int j = 0; j < D; j++) {
                if(t >= L[j] && t <= R[j]) {
                    if(T[i] >= L[j] && T[i] <= R[j]) {
                        d[i] = j + 1;
                        break;
                    }else {
                        if(T[i] > S[i]) {
                            t = R[j];
                        }else {
                            t = L[j];
                        }
                    }
                }
            }
        }
        N = N + 1;
        for(int i = 0; i < K; i++) {
            System.out.println(d[i]);
        }

    }
}