AtCoder Regular Contest 082: D - Derangement

,

http://arc082.contest.atcoder.jp/tasks/arc082_b

solution

なにか貪欲っぽく。$O(N)$。

$i$を$p_i = i$なものの中で最小として$(i, i+1)$でswapすることを繰り返す。 $p_i = i$であれば$p_{i+1} \ne i$であるので、swapすれば$p_i \ne i \land p_{i+1} \ne i+1$となる。 これより早く解決する方法はないのは明らか(本当か?)なのでこれでよい。

implementation

#!/usr/bin/env python3
n = int(input())
p = list(map(lambda p_i: int(p_i) - 1, input().split()))
result = 0
for i in range(n):
    if p[i] == i:
        j = i + 1
        if j >= n:
            j = i - 1
        p[i], p[j] = p[j], p[i]
        result += 1
print(result)