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

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

AtCoder ABC 154 C - Distinct or Not (300 点)

こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う

  1. std::set や std::map などの連想配列を用いて管理する
  2. ソートしてソート順に処理していく

問題へのリンク

問題概要

 N 個の整数  A_{1}, \dots, A_{N} が与えられる。この整数列のどの 2 つの要素も互いに異なるならば YES を、そうでないなら NO を出力せよ。

制約

  •  2 \le N \le 2 \times 10^{5}

解法(1): std::set を用いる

std::set を用いると、以下の処理をそれぞれ  O(\log{N}) でこなすことができる。

  • データ構造に要素 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;
}