【AtCoder】ABC 408 C - Not All Covered | 緑コーダーが解くAtCoder

atcoder.jp

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 223 / NoviSteps: 3Q

問題概要
制約
考察
実装例
コメント

問題概要

番号が付けられた $N$ 個の城壁と $M$ 個の砲台があり、砲台 $i$ は $L_i$ 以上 $R_i$ 以下の番号の城壁を守っている。

ある砲台を破壊すると、その砲台が守っていた城壁はその砲台により守られなくなる。どの砲台にも守られていない城壁が存在する状態にするためには、最小で何個の砲台を破壊する必要があるか求めよ。

制約

$1 \leq N \leq 10^6$
$1 \leq M \leq 2 \times 10^5$
入力はすべて整数

考察

各城壁が何個の砲台によって守られているのかを記録しておけば、その和の最小値を取ることによって、破壊すべき砲台の個数を求めることができる。

具体的には、下図の $c_i$ のような配列の最小値を求めればよい。

さて、上に示したようなテーブルを作っていく過程において、各砲台の守備範囲 $[L_i, R_i ]$ について1マスずつフラグを立てていくのでは計算量が $O(NM)$ となって TLE してしまう。

そこで、imos法を用いてこの処理を効率化しよう。

詳細な実装は実装例を参照してほしい。これで計算量は $O(N + M)$ に落とすことができた。

実装例

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr int INF = 1e+9;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    vector<int> c(N + 2, 0);
    rep(i, 0, M)
    {
        int L, R;
        cin >> L >> R;
        c[L]++;
        c[R + 1]--;
    }

    rep(i, 1, N + 1) c[i] += c[i - 1];

    int ans = INF;
    rep(i, 1, N + 1)
    {
        chmin(ans, c[i]);
    }

    cout << ans << endl;

    return 0;
}