【競プロ】1日1AC : ABC14 C問題

今日で6日目です。今日の問題はあるアルゴリズムを使うと楽に解けるよ、とオススメしてもらったので勉強がてら解いたものです。

Difficultyは1283（水）です。（推定値なので実際の難易度とズレがある可能性があります）
（AtCoder Problemsより）

diffは高めですが諦めずに解いてみてください。

提出コードと考えたこと

まずアルゴリズムについて。累積和を用いるのですが、その中でもいもす法と呼ばれる物が非常に便利です。リンク先の１次元０次いもす法を見てください。
問題例とこの問題はほぼ同じです。

以下は提出コードです。

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

const int TYPE = 1000000;

int main(){
    int n;
    cin >> n;
    vector<int> s(TYPE + 1,0);
    for(int i = 0;i < n;i++){
        int a,b;
        cin >> a >> b;
        s[a]++; s[b + 1]--;
    }
    for(int i = 0;i < TYPE;i++) s[i + 1] += s[i];
    auto iter = max_element(s.begin(),s.end());
    cout << *iter << endl;
    return 0;
}

計算量の面で工夫は必要ですが、発想自体は単純です。ある絵具を何人が選んだかを \(1,-1\) の区間で記録しておき、累積和である絵具が何人に選ばれたのかを計算します。

余談ですが、配列から最大値を取り出すのにイテレータを利用する方法を覚えました。（16行目）