【AtCoder】ABC 346 C - Σ | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 179

問題概要

長さ の正整数列 と正整数 が与えられる。 以上 以下の正整数のうち、 の中に一度も現れないものの総和を求めよ。

制約

• 入力はすべて整数
• 
• 

考察

なので、 から までの数について各々が に含まれるかどうかを判定していくのは厳しい。

そこで、 の要素数 が比較的小さいことに注目して、 から までの数の総和から に1回以上現れる 以上 以下の要素を引けばよい。このとき、 には要素の重複があり得るので、setやmapを使って要素の種類だけを考えなければらない。

ここではsetの方がより適切か。

コード

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

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

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

int main()
{
   ll N, K;
    cin >> N >> K;
    map<ll, ll> mp;
    rep(i, 0, N)
    {
        ll A;
        cin >> A;
        mp[A]++;
    }

    ll sum = K * (K + 1) / 2;
    for (auto &&m : mp)
    {
        if (m.first > K)
            break;

        sum -= m.first;
    }

    cout << sum << endl;
}

atcoder.jp

実装時間: 10分