SRM397 DIV2 Level.1

適当に解いたらタイムアウト。
一度試したパターンは飛ばすように書き換えたら普通に通った。

public class Pair<T, U>
{
    public Pair()
    {
    }

    public Pair(T first, U second)
    {
        this.First = first;
        this.Second = second;
    }

    public T First;
    public U Second;
}

public class SortingGame
{
    bool isSorted(int[] array)
    {
        bool isSorted = true;
        for (int i = 1; i < array.Length; i++)
        {
            if (array[i - 1] >= array[i])
            {
                isSorted = false;
                break;
            }
        }
        return isSorted;
    }
    int getSig(int[] array)
    {
        int ret = 0;
        for (int i = 0; i < array.Length; i++)
        {
            ret += array[i];
            ret *= 10;
        }
        return ret;
    }
    
    public int fewestMoves(int[] board, int k)
    {
        int size = board.Length;
        Pair<int[], int> p = new Pair<int[], int>();
        p.First = (int[])board.Clone();
        p.Second = 0;

        Queue<Pair<int[], int>> q = new Queue<Pair<int[], int>>();
        q.Enqueue(p);

        Dictionary<int, int> dic = new Dictionary<int, int>();

        while (q.Count != 0)
        {
            Pair<int[], int> hoge = q.Dequeue();
            int sig = getSig(hoge.First);
            if (dic.ContainsKey(sig))
            {
                continue;
            }
            else
            {
                dic[sig] = 1;
            }

            if (isSorted(hoge.First))
            {
                return hoge.Second;
            }
            for (int i = 0; i <= size - k; i++)
            {
                Pair<int[], int> p2 = new Pair<int[], int>();
                p2.First = (int[])hoge.First.Clone();
                p2.Second = hoge.Second + 1;
                Array.Reverse(p2.First, i, k);
                q.Enqueue(p2);
            }
        }
        return -1;
    }
}