C - Σ Editorial by yuto1115
解説\(K\) が大きいため、\(1,2,\dots,K\) のうち \(A\) に含まれないものを \(1\) つずつ足し合わせていくことはできません。そこで、以下の方針を考えます。
- \(\mathrm{ans}=1+2+\dots+K=\frac{K(K+1)}{2}\) とする。
- \(A\) の中に一度以上現れる \(1\) 以上 \(K\) 以下の整数を列挙し、 それぞれの整数を \(\mathrm{ans}\) から引く。
- \(\mathrm{ans}\) を出力する。
\(A\) の中に一度以上現れる \(1\) 以上 \(K\) 以下の整数を列挙するためには、\(A\) から \(K+1\) 以上の数を除外した上で、重複を取り除く必要があります。重複を取り除く方法は複数考えられますが、例えば、 C++ の std::set
や Python の set などの集合を管理できるデータ構造を使う方法があります。これらのデータ構造は、挿入された要素を重複を取り除いた状態で管理してくれます(それ以外の機能を持つものもあります)。より詳細には、C++ の std::set
のような内部に平衡二分探索木を用いたものと、C++ の std::unordered_set
や Python の set のようなハッシュを用いたものがあり、両者は計算量や機能の面で差があります。本問題においてはどちらも用いることができ、前者を用いると計算量が \(O(N\log N)\)、後者を用いると計算量が期待 \(O(N)\) になりますが、後者の場合はハッシュの衝突によって計算量が悪化する可能性もあることを念頭に入れて使用してください。以下の実装例では C++ の std::set
を用いています。
実装例 (C++) :
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, k;
cin >> n >> k;
set<int> st;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
if (a <= k) st.insert(a);
}
ll ans = (ll) k * (k + 1) / 2;
for (int i: st) ans -= i;
cout << ans << endl;
}
posted:
last update: