第12回PAST H ３種の硬貨

問題へのリンク

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

    struct ABCInfoDef
    {
        internal long A;
        internal long B;
        internal long C;
    }
    static List<ABCInfoDef> mABCInfoList = new List<ABCInfoDef>();

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

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

        SplitAct(InputList[0]);
        long X = wkArr[1];
        long UB = X;

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABCInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            WillAdd.C = wkArr[2];
            mABCInfoList.Add(WillAdd);
        }

        // スコア[銅の数]なインラインDP表
        long?[] DPArr = new long?[UB + 1];
        DPArr[0] = DeriveScore(0, 0);

        foreach (ABCInfoDef EachABCInfo in mABCInfoList) {
            for (long I = UB; 0 <= I; I--) {
                if (DPArr[I].HasValue == false) continue;

                long NewI = I + EachABCInfo.B;
                if (NewI > UB) continue;

                long CurrKin;
                long CurrGin;
                DeriveKinGin(DPArr[I].Value, out CurrKin, out CurrGin);

                long NewKin = CurrKin + EachABCInfo.C;
                long NewGin = CurrGin + EachABCInfo.A;
                long NewScore = DeriveScore(NewKin, NewGin);

                if (DPArr[NewI].HasValue) {
                    if (DPArr[NewI] >= NewScore) {
                        continue;
                    }
                }
                DPArr[NewI] = NewScore;
            }
        }

        long MaxScore = long.MinValue;
        for (long I = 0; I <= UB; I++) {
            if (DPArr[I].HasValue) {
                MaxScore = Math.Max(MaxScore, DPArr[I].Value);
            }
        }

        for (long I = 0; I <= UB; I++) {
            if (DPArr[I].HasValue) {
                if (DPArr[I] == MaxScore) {
                    long Kin;
                    long Gin;
                    DeriveKinGin(DPArr[I].Value, out Kin, out Gin);
                    Console.WriteLine("{0} {1} {2}", Kin, 1000000000 - Gin, X - I);
                    break;
                }
            }
        }
    }

    const long Geta = 100000000;

    // 金の数と銀の数を引数として、スコアを返す
    static long DeriveScore(long pKin, long pGin)
    {
        long WillReturn = 0;
        WillReturn += pKin * Geta;
        WillReturn += (Geta - 1) - pGin;
        return WillReturn;
    }

    // スコアを引数として、金の数と銀の数を設定
    static void DeriveKinGin(long pScore, out long pKin, out long pGin)
    {
        pKin = pScore / Geta;

        pScore %= Geta;
        pGin = (Geta - 1) - pScore;
    }
}

解説

金、銀、銅
の順に価値が高いので、

スコア[銅の数]なインラインDPで解けます。