ABC-072-D Derangement

■■■問題■■■

1,2, ・・・ ,N からなる順列 p1,p2, ・・・ ,pN が与えられます。
次の操作を何回か (0回でもよい) 行うことが出来ます。

操作: 順列で隣り合う2つの数を選んでスワップする。

何回か操作を行って、任意の 1 <= i <= N に対して pi != i となるようにしたいです。
必要な操作の最小回数を求めてください。

■■■入力■■■

N
p1 p2  ・・・  pN

●2 <= N <= 10万
●p1,p2, ・・・ ,pN は 1,2, ・・・ ,N の順列である

■■■出力■■■

必要な操作の最小回数を出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5");
            WillReturn.Add("1 4 3 5 2");
            //2
            //1と4を入れ替え、その後1と3を入れ替えることで p は 4,3,1,5,2 となり、
            //これは条件を満たします。
            //これが最小回数なので、答えは2となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 2");
            //1
            //1と2を入れ替えれば条件を満たします。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2");
            WillReturn.Add("2 1");
            //0
            //初めから条件を満たしています。
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("9");
            WillReturn.Add("1 2 4 9 5 8 7 3 6");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] PArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        int Answer = 0;
        for (int I = 0; I <= PArr.GetUpperBound(0); ) {
            if (PArr[I] != I + 1) {
                I++;
                continue;
            }

            Answer++;
            I += 2;
        }
        Console.WriteLine(Answer);
    }
}

解説

1 2 4 9 5 8 7 3 6 を完全順列にするのに必要な最小の交換回数は
2 1 4 9 8 5 3 7 6 のように交換すれば2回となります。

1 2 3 4 を完全順列にするのに必要な最小の交換回数は
2 1 4 3 のように交換すれば2回となります。

完全順列に反する要素をNG
完全順列を満たす要素をOK
と表すことにし、

要素を順に見ていき、完全順列に反する要素が登場したら、次の要素と交換すれば、
NG OKの場合でも、NG NGの場合でも
交換後は、OK OKとなります。

後は、上記の最適手順での交換回数を求めれば、解となります。