問題概要

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;
}