D: Derangement - AtCoder Regular Contest 082
順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。
p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ l に対して、この部分列をすべてp[i] ≠ l となるようにするにはペアを作って l / 2(小数以下切り捨て)回で可能である。これは、最初から順にペアを作ってそれらをSwapしていけば偶数この場合はすべて条件をみたすようにでき、奇数個の場合は最後の1個を、その次のp[i] ≠ iであるような要素と入れ替えれば条件を満たすことができるからである。終端にちょっとだけ注意する。
よって、p[i]の中でp[i] = iとなるような部分列を抽出し、(int)(l / 2) を足していけばよい。O(N)。
