問題概要

$N$ 個の区間がある。各区間は 4 タイプあり、

タイプ 1：区間 $\lbrack l, r \rbrack$
タイプ 2：区間 $\lbrack l, r)$
タイプ 3：区間 $(l, r \rbrack$
タイプ 4：区間 $(l, r)$

となっている。これらの区間の組のうち、共通部分をもつものの個数を求めよ。

制約

$2 \le N \le 2000$

考えたこと

$O(N^{2})$ の計算量の解法で構わないので、純粋に 2 つの区間が共通部分をもつかどうかを判定できればよい。

考えやすいようにするために、できれば「左閉区間・右開区間」となるように揃えたい。そこで、0.5 を導入することで、次のようにしてもよい。

タイプ 1：区間 $\lbrack l, r \rbrack$ → 区間 $\lbrack l, r + 0.5)$
タイプ 2：区間 $\lbrack l, r)$ → 区間 $\lbrack l, r)$
タイプ 3：区間 $(l, r \rbrack$ → 区間 $\lbrack l + 0.5, r + 0.5)$
タイプ 4：区間 $(l, r)$ → 区間 $\lbrack l + 0.5, r)$

このように修正しても、共通部分をもつかどうかは変わらない。あとは、共通部分をもつかどうかを次の問題の方法と同様に check すればよい。

drken1215.hatenablog.com

コード

浮動小数点型はあまり扱いたくないため、全体を 2 倍して整数値のみで解いた。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> t(N), l(N), r(N);
    for (int i = 0; i < N; ++i) {
        cin >> t[i] >> l[i] >> r[i];
        l[i] *= 2, r[i] *= 2;
        if (t[i] == 1) ++r[i];
        else if (t[i] == 3) ++l[i], ++r[i];
        else if (t[i] == 4) ++l[i];
    }
    
    int res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            int L = max(l[i], l[j]);
            int R = min(r[i], r[j]);
            if (L < R) ++res;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 207 C - Many Segments (4Q, 灰色, 300 点)

問題概要

制約

考えたこと

コード