ARC082 D : Derangement(400)
作成日：2017.09.03
最終更新日：2017.09.03
問題概要
$1,2,...,N$の順列$p_1,p_2,...p_N$が与えられる。
操作「順列で隣り合う二つの数を選んで入れ替える」を$0$回以上行うことで、すべての$i$において$p_i \neq i$となるようにする。
必要な操作の最小回数を求めよ。
制約
$2 \leq N \leq 10^5$
数列$\{p_i\}$は$1,2,...,N$の順列
考え方
$p_i = i$である時は$p_{i-1}$あるいは$p_{i+1}$と入れ替えなければならない。
この時$p_{i-1} \neq i , p_{i+1} \neq i$であることから、$p_i$に対しては1回だけ操作を行えば良い。
また、それによって新たに操作を行わなければならない要素は生じない。
よって$p_i = i$となる$i$の個数だけ操作を行えば良い。
但し$p_i = i$かつ$p_{i+1} = i+1$の時はこの2つの要素を選んで操作を行うことで操作の回数を1回減らすことができる。
以上より、先頭から要素を見ていき$p_i = i$となるものが現れたら$p_{i+1}$と操作を行うことを繰り返せば良いことが分かる。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
int p[MC];
int main(){
scanf("%d" , &N);
repp(i,1,N+1){
scanf("%d" , p + i);
}
int ans = 0;
repp(i,1,N+1){
if(p[i] == i){
++ans;
++i;
}
}
printf("%d\n" , ans);
return 0;
}解法まとめ
先頭から要素を見ていき$p_i = i$となるものが現れたら$p_{i+1}$と操作を行う。(10-17行)