AtCoder BC072 D: Derangement

問題

D - Derangement
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

左から順にpiをみていきます。

・pi ≠ iの時
何もせずに、右に1つ進む

・pi = iの時
次の数と入れ替えて、右に2つ進む。このとき、次の数(pi+1)がi+1かどうかは特に意識する必要は無い。どちらの場合も、入れ替え後に条件を満たすため。

 なお、数列の右端がpi = iの場合は、一つ前の数と入れ替えればOK。

以上です。

ちょっと400点とは思えないほど簡単です。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;
 
typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;
    cin >> N;

    int p[N];

    REP(i,N)cin >> p[i];

    int i = 0;
    int ans = 0;
    while(i < N){
        if(p[i] == i + 1){
            ans += 1;
            i += 2;
        }else{
            i++;
        }
    }

    cout << ans << endl;
}

コメント

タイトルとURLをコピーしました