AGC044-A Pay to Win

問題へのリンク

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("5");
            WillReturn.Add("11 1 2 4 8");
            WillReturn.Add("11 1 2 2 8");
            WillReturn.Add("32 10 8 5 4");
            WillReturn.Add("29384293847243 454353412 332423423 934923490 1");
            WillReturn.Add("900000000000000000 332423423 454353412 934923490 987654321");
            //20
            //19
            //26
            //3821859835
            //23441258666
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NABCDInfoDef
    {
        internal long N;
        internal long A;
        internal long B;
        internal long C;
        internal long D;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

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

        var NABCDInfoList = new List<NABCDInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            NABCDInfoDef WillAdd;
            WillAdd.N = wkArr[0];
            WillAdd.A = wkArr[1];
            WillAdd.B = wkArr[2];
            WillAdd.C = wkArr[3];
            WillAdd.D = wkArr[4];
            NABCDInfoList.Add(WillAdd);
        }

        foreach (NABCDInfoDef EachNABCDInfo in NABCDInfoList) {
            long CurrN = EachNABCDInfo.N;
            long CurrA = EachNABCDInfo.A;
            long CurrB = EachNABCDInfo.B;
            long CurrC = EachNABCDInfo.C;
            long CurrD = EachNABCDInfo.D;
            MemoDict.Clear();
            long Answer = DFS(CurrN, CurrA, CurrB, CurrC, CurrD);
            Console.WriteLine(Answer);
        }
    }

    static SortedDictionary<long, long> MemoDict = new SortedDictionary<long, long>();

    // メモ化再帰で現在値がpKの時の、0までのコストを返す
    static long DFS(long pK, long pA, long pB, long pC, long pD)
    {
        if (pK == 0) return 0;
        if (pK == 1) return pD;

        if (MemoDict.ContainsKey(pK)) {
            return MemoDict[pK];
        }

        var SeniList = new List<long>();

        // 不等式でオーバフローのチェック
        if (Math.Abs(pK) <= long.MaxValue / pD) {
            SeniList.Add(Math.Abs(pK) * pD);
        }

        Action<long, long> KagenAndDiv = (pPlusMinus, pDivisor) =>
        {
            long Cost = 0;
            long NewK = pK;
            while (NewK % pDivisor > 0) {
                NewK += pPlusMinus;
                Cost += pD;
            }
            NewK /= pDivisor;
            if (pDivisor == 2) Cost += pA;
            if (pDivisor == 3) Cost += pB;
            if (pDivisor == 5) Cost += pC;
            SeniList.Add(Cost + DFS(NewK, pA, pB, pC, pD));
        };

        KagenAndDiv(-1, 2);
        KagenAndDiv(+1, 2);
        KagenAndDiv(-1, 3);
        KagenAndDiv(+1, 3);
        KagenAndDiv(-1, 5);
        KagenAndDiv(+1, 5);
        return MemoDict[pK] = SeniList.Min();
    }
}

解説

0からNに遷移させるのではなく
Nから0に遷移させるコストを考えます。

-1して0にする遷移
+1を繰り返し、2の倍数になったら2で割る遷移
-1を繰り返し、2の倍数になったら2で割る遷移
+1を繰り返し、3の倍数になったら3で割る遷移
-1を繰り返し、3の倍数になったら3で割る遷移
+1を繰り返し、5の倍数になったら5で割る遷移
-1を繰り返し、5の倍数になったら5で割る遷移
の7通りの遷移で、メモ化再帰で解いてます。