第6回PAST N 活動

問題へのリンク

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("4 6");
            WillReturn.Add("4 1");
            WillReturn.Add("3 2");
            WillReturn.Add("2 3");
            WillReturn.Add("1 4");
            //45
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 6");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            WillReturn.Add("3 3");
            WillReturn.Add("4 4");
            //30
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("16 100");
            WillReturn.Add("18 17");
            WillReturn.Add("5 18");
            WillReturn.Add("7 2");
            WillReturn.Add("5 8");
            WillReturn.Add("6 2");
            WillReturn.Add("16 16");
            WillReturn.Add("2 18");
            WillReturn.Add("13 17");
            WillReturn.Add("18 10");
            WillReturn.Add("11 10");
            WillReturn.Add("17 8");
            WillReturn.Add("1 2");
            WillReturn.Add("20 7");
            WillReturn.Add("4 11");
            WillReturn.Add("7 15");
            WillReturn.Add("2 1");
            //9282
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // ソートを定義した構造体
    ////////////////////////////////////////////////////////////////
    struct ActInfoDef : IComparable<ActInfoDef>
    {
        internal long Score;
        internal long Cost;

        public int CompareTo(ActInfoDef pOtherIns)
        {
            long Sahen = Score * pOtherIns.Cost;
            long Uhen = Cost * pOtherIns.Score;
            return Uhen.CompareTo(Sahen);
        }
    }
    static List<ActInfoDef> mActInfoList = new List<ActInfoDef>();

    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 HP = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ActInfoDef WillAdd;
            WillAdd.Score = wkArr[0];
            WillAdd.Cost = wkArr[1];
            mActInfoList.Add(WillAdd);
        }
        mActInfoList.Sort();

        var AnswerList = new List<long>();

        // 1個しか選ばない場合
        AnswerList.Add(HP * mActInfoList.Max(pX => pX.Score));

        // 複数選ぶ場合は、01ナップサック問題
        long UB = HP;

        // 最大スコア[HP]なインラインDP表
        long?[] DPArr = new long?[UB + 1];
        DPArr[HP] = 0;

        foreach (ActInfoDef EachActInfo in mActInfoList) {
            for (long I = 1; I <= UB; I++) {
                if (DPArr[I].HasValue == false) continue;

                long NewI = I - EachActInfo.Cost;
                long NewVal = DPArr[I].Value + I * EachActInfo.Score;

                AnswerList.Add(NewVal);
                if (NewI <= 0) {
                    continue;
                }
                if (DPArr[NewI].HasValue) {
                    if (DPArr[NewI].Value >= NewVal) {
                        continue;
                    }
                }
                DPArr[NewI] = NewVal;
            }
        }
        Console.WriteLine(AnswerList.Max());
    }
}

解説

場合に分けて考えます。

1つの活動のみ行う場合
この場合は、aが最大の活動を行うのが最適です。

2つ以上の活動を行う場合
今の体力をHP
活動1を{a1,b1}
活動2を{a2,b2}
とし、
a1 * HP + a2*(HP-b1) >= a2 * HP + a1*(HP-b2)
⇔
-a2*b1 >= -a1*b2
⇔
a1*b2 >= a2*b1
⇔
a1 / b1 >= a2 / b2
なので
a1/b1 の降順に活動するのが最適だと分かります。

後は、ソートを定義できる構造体でa1/b1 の降順に
誤差を気を付けてソートし、
最大スコア[現在HP]を更新するインラインDPで解けます。