ABC231-E Minimal payments

問題へのリンク

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 87");
            WillReturn.Add("1 10 100");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 49");
            WillReturn.Add("1 7");
            //7
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 123456789012345678");
            WillReturn.Add("1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000");
            //233
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long X = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        // 最小コスト[現在値]なDP表
        var PrevDP = new Dictionary<long, long>();
        PrevDP[X] = 0;

        int UB = AArr.GetUpperBound(0);
        for (int I = 0; I <= UB; I++) {
            long CurrA = AArr[I];

            var CurrDP = new Dictionary<long, long>();
            foreach (var EachPair in PrevDP) {
                Action<long, long> UpdateAct = (pNewKey, pNewVal) =>
                {
                    if (CurrDP.ContainsKey(pNewKey) == false
                        || CurrDP[pNewKey] > pNewVal) {
                        CurrDP[pNewKey] = pNewVal;
                    }
                };

                long CurrVal = EachPair.Key;
                if (I < UB) {
                    CurrVal %= AArr[I + 1];
                }

                // 直接払う場合
                long Div = CurrVal / CurrA;
                long NewKey1 = EachPair.Key - Div * CurrA;
                long NewVal1 = EachPair.Value + Div;
                UpdateAct(NewKey1, NewVal1);

                // 上位桁で払って、おつりをもらう場合
                if (I < UB) {
                    long NextA = AArr[I + 1];
                    long RestVal = NextA - CurrVal;
                    long NewKey2 = EachPair.Key - CurrVal + NextA;
                    long NewVal2 = EachPair.Value + RestVal / AArr[I];
                    UpdateAct(NewKey2, NewVal2);
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(PrevDP[0]);
    }
}

解説

例えば
1円,5円,10円,100円,500円
で379円払う場合を考えると

9円を最小コストで払って
70円を最小コストで払って
300円を最小コストで払えば
解になると分かります。

払い方は、直接払うか、上位硬貨で払っておつりを貰うかの
2通りしかないので、

最小コスト[現在値]なDPで解けます。