問題概要

長さ $N$ の整数列 $A_{1}, A_{2}, \dots, A_{N}$ と、正の整数 $K$ が与えられる。

$1$ 以上 $K$ 以下の整数のうち、数列 $A$ に一度も含まれないものについての総和を求めよ。

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le K, A_{i} \le 2 \times 10^{9}$

考えたこと

まず、 $1 + 2 + \dots + K = \frac{K(K+1)}{2}$ となる。

この値から「1 以上 $K$ 以下の整数のうち、数列 $A$ に一度以上含まれるもの」の総和を引くことにしよう。

さて、この「1 以上 $K$ 以下の整数のうち、数列 $A$ に含まれる整数」をすべて求めるためには、集合型（set 型）を活用するのがよいだろう。

C++ の set 型の変数 S に対して、整数 x を挿入する操作は

S.insert(x);

と書ける。重複は自動的に除外してくれる！！！　数列 $A$ に含まれる整数のうち $1$ 以上 $K$ 以下であるものをすべて S に挿入しよう。

そして、集合 S に含まれる要素を順に調べていき、その総和を求めればよい。そのような操作は次のように書ける。

long long sub = 0;
for (auto x : S) sub += x;

最後に計算量を見積もる。集合 S に要素 x を挿入する処理の計算量は $O(\log N)$ である。それを高々 $N$ 回実行するので、計算量は $O(N \log N)$ となる。

コード

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

int main() {
    long long N, K, A;
    cin >> N >> K;
    set<long long> S;
    for (int i = 0; i < N; i++) {
        cin >> A;
        if (A <= K) S.insert(A);
    }

    long long all = K * (K + 1) / 2, sub = 0;
    for (auto x : S) sub += x;
    cout << all - sub << endl;
}

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

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

AtCoder ABC 346 C - Σ (5Q, 灰色, 250 点)

問題概要

制約

考えたこと

コード