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

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

AtCoder ABC 205 B - Permutation Check (7Q, 灰色, 200 点)

いろんな方法が考えられる!

問題概要

1 以上  N 以下の整数からなる数列  A_{1}, A_{2}, \dots, A_{N} が与えられます。

この数列が  (1, 2, \dots, N) を並び替えられることで得られるかどうかを判定せよ。

制約

  •  1 \le N \le 1000

考えたこと

問題文は「 (1, 2, \dots, N) を並び替えることで  A_{1}, A_{2}, \dots, A_{N} に一致させられるか」を問いかけるものです。

しかしながら、逆転の発想で、 A_{1}, A_{2}, \dots, A_{N} の方を並び替えることを考えましょう。特に、小さい順に並び替えることを考えます。

数列  A_{1}, A_{2}, \dots, A_{N} を並び替えることで、 (1, 2, \dots, N) となるならば Yes、そうならなければ No と判定できます。

コード

#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());
    
    // {1, 2, ..., N} の配列を作る
    vector<int> B(N);
    for (int i = 0; i < N; i++) {
        B[i] = i + 1;
    }
    
    if (A == B) cout << "Yes" << endl;
    else cout << "No" << endl;
}