こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う
- std::set や std::map などの連想配列を用いて管理する
- ソートしてソート順に処理していく
問題概要
個の整数 が与えられる。この整数列のどの 2 つの要素も互いに異なるならば YES を、そうでないなら NO を出力せよ。
制約
解法(1): std::set を用いる
std::set を用いると、以下の処理をそれぞれ でこなすことができる。
- データ構造に要素 v を挿入する
- データ構造の中に要素 v があるかどうかを判定する
データ構造の変数を s とすると、前者は s.insert(v)、後者は if (s.count(v)) で書くことができる。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; set<int> s; bool ok = true; for (int i = 0; i < N; ++i) { int a; cin >> a; // a がすでにあるかどうか (すでにあったらダブりがある) if (s.count(a)) ok = false; // a を挿入 s.insert(a); } if (ok) cout << "YES" << endl; else cout << "NO" << endl; }
解法 (2):ソートする
この手の「どの要素が何個あるか」というのを扱いたい問題で、ソートするのも有力だ。A をソート済みとする。
- もしダブりがあるなら、たとえば 2, 3, 4, 4, 6, 7 とかで 4 の連続がある (A[i] == A[i+1] となる箇所があるはず)
- ダブりがないなら、A[i] == A[i+1] となることはない
というわけで、A[i] == A[i+1] となる瞬間があるかどうかを調べればOK。
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; sort(A.begin(), A.end()); // ソート bool ok = true; for (int i = 0; i + 1 < N; ++i) { if (A[i] == A[i+1]) ok = false; } if (ok) cout << "YES" << endl; else cout << "NO" << endl; }