AtCoderBeginnerContest072 D 問題 400 点 「Derangement」

問題リンク

問題概要

制約

解法

条件を満たしている要素と満たしていない要素が隣り合っていた時，スワップしていくことを前から順に行うことでどちらも条件を満たすことができる。並びが逆でも，どちらも条件を満たしていない場合でも同じことをすればすべての要素で条件を満たせる。

お気持ち

すごいな～～～思いつかんかった。

AC コード

# coding: utf-8
N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(N-1):
    if i + 1 == P[i]:
        P[i], P[i+1] = P[i+1], P[i]
        ans += 1
if P[N-1] == N:
    ans += 1

print(ans)