ARC160-A Reverse and Count

問題へのリンク

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("3 5");
            WillReturn.Add("1 3 2");
            //2 3 1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 15");
            WillReturn.Add("1 2 3 4 5");
            //5 4 3 2 1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 37");
            WillReturn.Add("9 2 1 3 8 7 10 4 5 6");
            //9 2 1 6 5 4 10 7 8 3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mK;
    static long[] mAArr;
    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mK = wkArr[1];

        mAArr = GetSplitArr(InputList[1]);
        UB = mAArr.GetUpperBound(0);

        for (long I = 0; I <= UB; I++) {
            long Shikii = mAArr[I];
            long[] LowerValArr = GetLowerValArr(I + 1, Shikii);

            long RestLen = mAArr.Length - (I + 1);
            long SameCnt = mAArr.Length + (RestLen) * (RestLen - 1) / 2;

            long[] GreaterValArr = GetGreaterValArr(I + 1, Shikii);

            if (mK <= LowerValArr.Length) {
                // 反転区間が確定し、終了

                long RevL = I;

                Array.Sort(LowerValArr);
                long TargetVal = LowerValArr[mK - 1];
                long TargetInd = Array.IndexOf(mAArr, TargetVal);

                DeriveAnswer(RevL, TargetInd);
                return;
            }

            if (LowerValArr.Length + SameCnt < mK) {
                // 反転区間が確定し、終了

                long RevL = I;

                Array.Sort(GreaterValArr);
                long Target = mK - LowerValArr.Length - SameCnt;
                long TargetVal = GreaterValArr[Target - 1];
                long TargetInd = Array.IndexOf(mAArr, TargetVal);

                DeriveAnswer(RevL, TargetInd);
                return;
            }

            mK -= LowerValArr.Length;
        }

        var AnswerList = new List<long>();
        for (long I = 0; I <= UB; I++) {
            AnswerList.Add(mAArr[I]);
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    // 反転区間を引数とし、解を出力
    static void DeriveAnswer(long pRevL, long pRevR)
    {
        var AnswerList = new List<long>();
        for (long I = 0; I <= UB; I++) {
            AnswerList.Add(GetVal(I, pRevL, pRevR));
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

    // 現在Ind,反転開始,反転終了を引数とし、現在値を返す
    static long GetVal(long pCurrInd, long pRevStaInd, long pRevEndInd)
    {
        if (pRevStaInd <= pCurrInd && pCurrInd <= pRevEndInd) {
            long Diff = pCurrInd - pRevStaInd;
            long TargetInd = pRevEndInd - Diff;
            return mAArr[TargetInd];
        }
        return mAArr[pCurrInd];
    }

    // 区間内の閾値未満の値の配列を返す
    static long[] GetLowerValArr(long pStaInd, long pShikii)
    {
        var WillReturn = new List<long>();
        for (long I = pStaInd; I <= UB; I++) {
            if (mAArr[I] < pShikii) {
                WillReturn.Add(mAArr[I]);
            }
        }
        return WillReturn.ToArray();
    }

    // 区間内の閾値超えの値の配列を返す
    static long[] GetGreaterValArr(long pStaInd, long pShikii)
    {
        var WillReturn = new List<long>();
        for (long I = pStaInd; I <= UB; I++) {
            if (mAArr[I] > pShikii) {
                WillReturn.Add(mAArr[I]);
            }
        }
        return WillReturn.ToArray();
    }
}

解説

辞書順でK番目なので、先頭の文字から決定していきます。

9 2 1 3 8 7 10 4 5 6
での辞書順で37番目の数列を考えます。

まず1番目が
9未満は8通り
9となるのが (10 + 9C2) 通り
9超えは0通り

なので1番目は9で確定し、
1番目が9での
37-8で25番目
の数列を求めれば良いと分かります。

次に2番目を考えます。
2未満は1通り
2になるのが (10 + 8C2) 通り
2超えは7通り

なので2番目は2で確定し、
1番目が9、2番目2での
37-8-1で24番目
の数列を求めれば良いと分かります。

同様に進めていけば、解を求めることができます。