ABC344-F Earn to Advance

問題へのリンク

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

    static long[,] mBanArr;
    static List<long[]> mYokoCostArrList = new List<long[]>();
    static List<long[]> mTateCostArrList = new List<long[]>();

    static long UB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);
        UB = N - 1;

        mBanArr = CreateBanArr(InputList.Skip(1).Take((int)N));

        foreach (string EachStr in InputList.Skip(1 + (int)N).Take((int)N)) {
            mYokoCostArrList.Add(EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray());
        }

        foreach (string EachStr in InputList.Skip(1 + (int)N + (int)N)) {
            mTateCostArrList.Add(EachStr.Split(' ').Select(pX => long.Parse(pX)).ToArray());
        }

        var InsPQueue = new PQueue();
        PQueue.PQueueJyoutaiDef WillEnqueue;
        WillEnqueue.CurrX = 0;
        WillEnqueue.CurrY = 0;
        WillEnqueue.ActCnt = 0;
        WillEnqueue.RestMoney = 0;
        WillEnqueue.MaxEarn = mBanArr[0, 0];
        InsPQueue.Enqueue(WillEnqueue);

        long Answer = long.MaxValue;

        var EdakiriDict = new Dictionary<long, long>();
        while (InsPQueue.IsEmpty() == false) {
            PQueue.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
            if (Dequeued.CurrX == UB && Dequeued.CurrY == UB) {
                Answer = Math.Min(Answer, Dequeued.ActCnt);
                continue;
            }

            if (Dequeued.ActCnt >= Answer) continue;

            long Hash = GetHash(Dequeued);
            long CurrSortKey = Dequeued.SortKey;
            if (EdakiriDict.ContainsKey(Hash)) {
                if (EdakiriDict[Hash] <= CurrSortKey) {
                    continue;
                }
            }
            EdakiriDict[Hash] = CurrSortKey;

            long CurrX = Dequeued.CurrX;
            long CurrY = Dequeued.CurrY;
            long CurrActCnt = Dequeued.ActCnt;
            long CurrRestMoney = Dequeued.RestMoney;
            long CurrMaxEarn = Dequeued.MaxEarn;

            Action<long, long> EnqueueAct = (pNewX, pNewY) =>
            {
                if (UB < pNewX || UB < pNewY) return;

                long PayMoney = DerivePayMoney(CurrX, CurrY, pNewX, pNewY);
                long NewRestMoney = CurrRestMoney - PayMoney;
                long NewActCnt = CurrActCnt + 1;

                if (NewRestMoney < 0) {
                    long Div = Math.Abs(NewRestMoney) / CurrMaxEarn;
                    if (Math.Abs(NewRestMoney) % CurrMaxEarn > 0) {
                        Div++;
                    }
                    NewActCnt += Div;
                    NewRestMoney += CurrMaxEarn * Div;
                }

                long NewMaxEarn = Math.Max(CurrMaxEarn, mBanArr[pNewX, pNewY]);

                WillEnqueue.CurrX = pNewX;
                WillEnqueue.CurrY = pNewY;
                WillEnqueue.ActCnt = NewActCnt;
                WillEnqueue.RestMoney = NewRestMoney;
                WillEnqueue.MaxEarn = NewMaxEarn;
                InsPQueue.Enqueue(WillEnqueue);
            };
            EnqueueAct(CurrX, CurrY + 1);
            EnqueueAct(CurrX + 1, CurrY);
        }
        Console.WriteLine(Answer);
    }

    static long GetHash(PQueue.PQueueJyoutaiDef pJyoutai)
    {
        long Hash = 0;
        Hash += pJyoutai.MaxEarn * 10000;
        Hash += pJyoutai.CurrX * 100;
        Hash += pJyoutai.CurrY;
        return Hash;
    }

    // 移動元座標と、移動先座標を引数として支払う金額を返す
    static long DerivePayMoney(long pFromX, long pFromY, long pToX, long pToY)
    {
        if (pFromX != pToX) {
            return mYokoCostArrList[(int)pFromY][pFromX];
        }
        else {
            return mTateCostArrList[(int)pFromY][pFromX];
        }
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をlongの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new long[0, 0];
        }

        long[] IntArr = { };
        Action<string> SplitAct = pStr =>
            IntArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(StrList[0]);

        long UB_X = IntArr.GetUpperBound(0);
        long UB_Y = StrList.Count - 1;

        long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];

        for (long Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[(int)Y]);
            for (long X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

#region PQueue
// 内部で配列使用の優先度付きキュー (根のValが最小)
internal class PQueue
{
    internal struct PQueueJyoutaiDef
    {
        internal long CurrX;
        internal long CurrY;
        internal long ActCnt;
        internal long RestMoney;
        internal long MaxEarn;

        internal long SortKey
        {
            get
            {
                return ActCnt * 1000000000 + 999999999 - RestMoney;
            }
        }
    }

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

    // コンストラクタ
    internal PQueue()
    {
        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--;

        MinHeapify(1);
        return TopNode;
    }

    // 根ノードを指定し、根から葉へヒープ構築
    private void MinHeapify(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;

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

解説

状態として持つのは
●X座標
●Y座標
●行動回数
●残金
●経路上での日給の最大値

ソートキーは、
行動回数 * 1000000000 + 999999999 - 残金
となります。

残金は、経路上での日給の最大値以下なのと、
行動回数を1増やすことで、
経路上での日給の最大値だけ
残金を増やせるので
行動回数が小さいほうが得であるからです。

後は、プライオリティーキューで早めに解を求めて
解を使った枝切りなどをしてます。