Note

サンタ・クララ在住エンジニアの勉強・生活の記録です

Atcoder Beginner Contest 106-D

ABC 106-D Atcoder Express 2の解説です。

この問題は累積和でとく問題なのですが、2次元で使う累積和が全くイメージできずコンテスト中に解けませんでした。僕は累積和をこう理解していました:

  • 数直線上に点があり、それを左から足してく
  • 答えを出すときはarr[Right] - arr[Left]

今回の問題は

  • 数直線ではなく2次元としてデータを保持する
  • 答えを出すのは引き算ではなく足し算

自分のイメージと異なる使い方のため、思いつくことも実装もできませんでした。また、電車の区間をどうやって保持したらいいのかもわからなかったです。

累積和を使わずに解くとこうなります。

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int M = in.nextInt();
    int Q = in.nextInt();

    int[][] map = new int[N + 1][N + 1];
    for (int i = 0; i < M; i++) {
        int L = in.nextInt();
        int R = in.nextInt();

        map[L][R] += 1;
    }

    for (int i = 0; i < Q; i++) {
        int p = in.nextInt();
        int q = in.nextInt();

        int answer = 0;

        for (int j = p; j <= q; j++) {
            for (int k = p; k <= q; k++) {
                answer += map[j][k];
            }
        }
    }
}

ただ、これだとO(QN2)なのでなんとか早く求めたい。

そこで横一列分を最初に加えといて、あとから加える累積和の方法を取るとO(N2 + QN)で実行できます。

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int N = in.nextInt();
    int M = in.nextInt();
    int Q = in.nextInt();

    int[][] map = new int[N + 1][N + 1];
    for (int i = 0; i < M; i++) {
        int L = in.nextInt();
        int R = in.nextInt();

        map[L][R] += 1;
    }

    for (int i = 0; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            map[i][j] += map[i][j - 1];
        }
    }

    for (int i = 0; i < Q; i++) {
        int P = in.nextInt();
        int q = in.nextInt();

        int answer = 0;
        for (int j = P; j <= q; j++) {
            answer += map[j][q];
        }

        System.out.println(answer);
    }
}
  1. 2次元配列で電車をとる
  2. とりあえず処理を書いてみる

この2つができれば累積和の解法にたどり着いた気がします。