Q07 ファイルの順番を元どおりに戻したい！

C#のソース

using System;

class Program
{
    static void Main()
    {
        Solve(3);
        Solve(15);
    }

    static void Solve(int pLen)
    {
        // 場合の数[移動が必要な最大の数 , 使用済数のBitSet]なDP表
        int AllBitOn = (1 << pLen) - 1;
        long[,] DPArr = new long[pLen + 1, AllBitOn + 1];
        DPArr[0, 0] = 1;
        for (int I = 1; I <= pLen; I++) {
            for (int J = pLen; 0 <= J; J--) {
                for (int K = AllBitOn; 0 <= K; K--) {
                    if (DPArr[J, K] == 0) continue;
                    for (int L = 1; L <= pLen; L++) {
                        int CurrBit = (1 << (L - 1));
                        if ((K & CurrBit) > 0) continue;

                        // 自分超えの値が左にあったら移動が必要
                        int NewJ = J;
                        if (K > CurrBit) {
                            NewJ = Math.Max(NewJ, L);
                        }
                        int NewK = K | CurrBit;

                        DPArr[NewJ, NewK] += DPArr[J, K];
                    }
                }
            }
        }

        long Answer = 0;
        for (int I = 1; I <= pLen; I++) {
            Answer += DPArr[I, AllBitOn] * I;
        }
        Console.WriteLine("長さ{0}での解は{1}", pLen, Answer);
    }
}

実行結果

長さ3での解は8
長さ15での解は17368162415924

解説

12534を
12345に並べ替える時の手数を考察すると
並べ替えが必要な数は、
自分超えの値が左にある数だと分かります。

後は、
場合の数[移動が必要な最大の数 , 使用済数のBitSet]
を更新するインラインDPで解けます。