[AtCoder] ABC 072 D – Derangement

2020年9月5日2020年12月13日

問題

方針

\( p_i = i \) となる \( i \) に対して、\( (p_i, p_{i+1}) = (p_{i+1}, p_i)\) と交換します。このとき、\( p_{i+1} = i \) となるので、交換によるロスはありません。\( p_N = N \) のときは、\( (p_{N-1}, p_N) = (p_N, p_{N-1}) \) と交換すれば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    int ans = 0;
    for (int i = 0; i < N - 1; i++) {
        if (p[i] == i + 1) {
            ans++;
            swap(p[i], p[i + 1]);
        }
    }
    if (p[N - 1] == N) {
        ans++;
    }
    cout << ans << "\n";
    return 0;
}