ABC440-E Cookies

問題へのリンク

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("2 4 3");
            WillReturn.Add("20 10");
            //80
            //70
            //60
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 100000 5");
            WillReturn.Add("-1 -1 -1");
            //-100000
            //-100000
            //-100000
            //-100000
            //-100000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 14142 13");
            WillReturn.Add("31 41 59 26 53 58 97 93 23");
            //1371774
            //1371770
            //1371766
            //1371762
            //1371758
            //1371754
            //1371750
            //1371746
            //1371742
            //1371738
            //1371736
            //1371735
            //1371734
        }
        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 mX;
    static long[] mAArr;
    static long UB;

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

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

        var Ins_PQueue_Arr = new PQueue_Arr();
        PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
        WillEnqueue.CntArr = new long[UB + 1];
        WillEnqueue.CntArr[0] = mK;
        WillEnqueue.SortKey = GetSum(WillEnqueue.CntArr);
        Ins_PQueue_Arr.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<string>();

        while (Ins_PQueue_Arr.Count() > 0) {
            PQueue_Arr.PQueueJyoutaiDef Dequeued = Ins_PQueue_Arr.Dequeue();

            if (mX > 0) {
                Console.WriteLine(Dequeued.SortKey);
                if (--mX == 0) {
                    return;
                }
            }

            Action<long> EnqueueAct = (pFromInd) =>
            {
                WillEnqueue.CntArr = (long[])Dequeued.CntArr.Clone();
                WillEnqueue.CntArr[pFromInd]--;
                WillEnqueue.CntArr[pFromInd + 1]++;
                WillEnqueue.SortKey = GetSum(WillEnqueue.CntArr);

                string Hash = GetHash(WillEnqueue.CntArr);
                if (VisitedSet.Add(Hash)) {
                    Ins_PQueue_Arr.Enqueue(WillEnqueue);
                }
            };

            for (long I = 0; I <= UB - 1; I++) {
                if (Dequeued.CntArr[I] > 0) {
                    EnqueueAct(I);
                }
            }
        }
    }

    static long GetSum(long[] pCntArr)
    {
        long Sum = 0;
        for (long I = 0; I <= UB; I++) {
            Sum += pCntArr[I] * mAArr[I];
        }
        return Sum;
    }

    static string GetHash(long[] pCntArr)
    {
        var sb = new System.Text.StringBuilder();
        for (long I = 0; I <= UB; I++) {
            sb.Append(pCntArr[I]);
            if (I < UB) {
                sb.Append(',');
            }
        }
        return sb.ToString();
    }
}

#region PQueue_Arr
// 内部で配列使用の優先度付きキュー (根のSortKeyが最大)
internal class PQueue_Arr
{
    internal struct PQueueJyoutaiDef
    {
        internal long[] CntArr;
        internal long SortKey;
    }

    private PQueueJyoutaiDef[] mHeapArr;
    private long mHeapArrCnt = 0;

    // コンストラクタ
    internal PQueue_Arr()
    {
        mHeapArr = new PQueueJyoutaiDef[65535];
    }

    internal bool IsEmpty()
    {
        return mHeapArrCnt == 0;
    }

    internal long Count()
    {
        return mHeapArrCnt;
    }

    internal long Peek()
    {
        return mHeapArr[1].SortKey;
    }

    // エンキュー処理
    internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
    {
        long CurrNode = 1 + mHeapArrCnt;
        if (mHeapArr.GetUpperBound(0) < CurrNode) {
            ExtendArr();
        }

        mHeapArr[CurrNode] = pAddJyoutai;
        mHeapArrCnt++;

        while (1 < CurrNode && mHeapArr[CurrNode / 2].SortKey < mHeapArr[CurrNode].SortKey) {
            PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
            mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
            mHeapArr[CurrNode / 2] = Swap;

            CurrNode /= 2;
        }
    }

    // 配列のExtend
    private void ExtendArr()
    {
        PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
        mHeapArr.CopyTo(NewHeapArr, 0);
        mHeapArr = NewHeapArr;
    }

    // デキュー処理
    internal PQueueJyoutaiDef Dequeue()
    {
        PQueueJyoutaiDef TopNode = mHeapArr[1];
        long LastNode = mHeapArrCnt;
        mHeapArr[1] = mHeapArr[LastNode];
        mHeapArrCnt--;

        MaxHeapify(1);
        return TopNode;
    }

    // 根ノードを指定し、根から葉へヒープ構築
    private void MaxHeapify(long pRootNode)
    {
        if (mHeapArrCnt <= 1) {
            return;
        }

        long Left = pRootNode * 2;
        long Right = pRootNode * 2 + 1;

        // 左の子、自分、右の子で値が最大のノードを選ぶ
        long Smallest = mHeapArr[pRootNode].SortKey;
        long SmallestNode = pRootNode;

        if (Left <= mHeapArrCnt && mHeapArr[Left].SortKey > Smallest) {
            Smallest = mHeapArr[Left].SortKey;
            SmallestNode = Left;
        }
        if (Right <= mHeapArrCnt && mHeapArr[Right].SortKey > Smallest) {
            Smallest = mHeapArr[Right].SortKey;
            SmallestNode = Right;
        }

        // 子ノードのほうが大きい場合
        if (SmallestNode != pRootNode) {
            PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
            mHeapArr[SmallestNode] = mHeapArr[pRootNode];
            mHeapArr[pRootNode] = Swap;

            // 再帰的に呼び出し
            MaxHeapify(SmallestNode);
        }
    }
}
#endregion

解説

A >= B >= C として100個取ると考えます。

(A,B,C) = (100 , 0 , 0) が明らかに1位です。
(A,B,C) = ( 99 , 1 , 0) が明らかに2位です。

そして、3位は(98,2,0)か(99,0,1)です。
どれか1つを右にひとつだけ移動させる遷移が次の候補になるので

後は、プライオリティキューを使用し、再訪防止のBFSで大きい値から求めていけば
解くことができます。