taiPyのお悩み解決ブログ

日々の発見をまとめます！

Javaの解答例： 競技プログラミングの鉄則 演習問題集 A07 - Event Attendance

目次

はじめに

競技プログラミングの鉄則という本を読み進めています。現在 Javaでコーディングしています。そんな中で、アルゴリズム以外でつまづくことがたくさんあったんですよね。なので、つまづいたポイントのメモを兼ねて、書いていきます。

ちなみに解答例として書かれているコードは私が書いたものです。公式の解答は参考文献よりご確認ください。

問題文

解答例

import java.util.Scanner;

public class Practice {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int D = sc.nextInt();
        int N = sc.nextInt();

        int[] L = new int[N + 2];
        int[] R = new int[N + 2];

        for (int i = 1; i <= N; i++) {
            L[i] = sc.nextInt();
            R[i] = sc.nextInt();
        }

        int[] upDown = new int[D + 2];
        for (int i = 1; i <= N; i++) {
            // +
            upDown[L[i]] ++;
            // -
            upDown[R[i] + 1] --;
        }

        int[] attendaceTable = new int[D + 2];
        for (int i = 1; i <= D; i++) {
            attendaceTable[i] = attendaceTable[i - 1] + upDown[i];
        }

        for (int j = 1; j <= D; j++) {
            System.out.println(attendaceTable[j]);
        }
    }
}

解説

また書きます。将来の自分よろしく！気が向いたときに。

2024/03/16追記 意外と「N + 2」や「D + 2」がポイント！これがないとサンプルではOKなんだけど、解としては間違になってましたねー。upDown[R[i] + 1] --;　の部分で　インデックスを+ 1してるんからですね。具体的に言うと、今回は、増減を使って参加人数を割り出しています。問題文としてはAさんは、Ｌ日目から R 日目まで参加します。ということは 人が減る時は、R + 1日目にAさんがいなくなりますよね。A さんが2日目から5日目まで参加するとしたら、2日目 （L日目）に Aさん（+ 1）が増えて、6日目（R + 1）にいなくなる（- 1）。

では、10日目になったときに、for がどう変化するのか。今回の対象部分はここ。

int[] upDown = new int[D + 2];
        for (int i = 1; i <= N; i++) {
            // +
            upDown[L[i]] ++;
            // -
            upDown[R[i] + 1] --;
        }

10日間 イベントが開催される時。D =10。

①アップダウンのインデックスが D +1の場合

upDownのインデックスは0から10。

D =10の時、upDown[R[i] + 1] --;がこうなる→upDown[11] --;

インデックスが10までしかないのに11を指定してしまったので、 はい。オーバー！！エラー！！

②D +2の場合 upDownのインデックスは0から11。

D =10の時、upDown[R[i] + 1] --;がこうなる→upDown[11] --;

インデックスが0から11で、今回11を指定した。何も問題がない。 はい。来た！！！Go, Go！！

だから N +2 や D +2 がポイントでした！

所感

最初は難しかったけれど、本を読む、実装する、理解する、説明する、復習する、復習する　⇐この流れを踏むと大体理解できるな。中学校や高校の数学を勉強している気分。できなくても、できるまで問題を解いたり、優しい問題から始めたりすれば、できた。それを愚直にやるだけ。

参考文献