🌿

競技プログラミングの鉄則 B09

2024/05/01に公開

C++

AtCoder

累積和

tech

累積和の応用問題

問題を要約

平面上に何枚かの紙を置いた時の紙の総面積を求める問題。
重なった部分は重複して数えない。
A09の類似問題。

つまづいたところ

これまでの鉄則本の二次元累積和の問題と異なり、座標はあくまで点を表している。
入力例の場合だと
$N = 2$
$(A_1, B_1, C_1, D_1) = (1, 1, 3, 3)$
$(A_2, B_2, C_2, D_2) = (2, 2, 4, 4)$

	1	2	3	4
0	0	0	0	0
1	+1	-1	0	0
2	-1	+1	0	0
3	0	0	+2	-1
4	0	0	-1	+1

ではなく、

	1	2	3	4
0	0	0	0	0
1	+1	0	-1	0
2	0	+1	0	-1
3	-1	0	+1	0
4	0	-1	0	+1

が正しい。(なぜか上と勘違いしていたが図示して理解できた。)
後は、A09同様に、
座標の出力T[i][j]の累積和を求めてやればいい。

実装

回答通りですが、一応コードも残しておきます。

#include <iostream>
using namespace std;

int N, T[1509][1509];
int A[100009], B[100009], C[100009], D[100009];

int main() {
    // 入力
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i] >> B[i] >> C[i] >> D[i];

    // 各紙について +1/-1を加算
    for (int i = 0; i <= 1500; i++) {
        for (int j = 0; j <= 1500; j++) T[i][j] = 0;
    }
    for (int i = 1; i <= N; i++) {
        // 座標で指示しているからCとDに+１していない。図示すればわかる。
        T[A[i]][B[i]] += 1;
        T[A[i]][D[i]] -= 1;
        T[C[i]][B[i]] -= 1;
        T[C[i]][D[i]] += 1;
    }
    // 二次元累積和をとる
    for (int i = 0; i <= 1500; i++) {
        for (int j = 1; j <= 1500; j++) T[i][j] = T[i][j - 1] + T[i][j];
    }
    for (int i = 1; i <= 1500; i++) {
        for (int j = 0; j <= 1500; j++) T[i][j] = T[i - 1][j] + T[i][j];
    }

    //面積を答える
    int Answer = 0;
    for (int i = 0; i <= 1500; i++) {
        for (int j = 0; j <= 1500; j++) {
            if (T[i][j] >= 1) Answer += 1;
        }
    }
    cout << Answer << endl;
    return 0;
}

他の解法を見ると、vector表記が多いのでvector表記での書き方も覚えていきたいです。

問題を要約

つまづいたところ

実装

Discussion