yukicoder 3329 Only the Rightest Choice is Right!!!

問題へのリンク

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

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct ItemInfoDef
    {
        internal long Score;
        internal long Weight;
    }
    static ItemInfoDef[] mItemInfoArr;

    static long UB;
    static long mWeightLimit;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mWeightLimit = wkArr[1];

        long[] ValueArr = GetSplitArr(InputList[1]);
        long[] WeightArr = GetSplitArr(InputList[2]);

        var ItemInfoList = new List<ItemInfoDef>();
        for (long I = 0; I <= ValueArr.GetUpperBound(0); I++) {
            ItemInfoDef WillAdd;
            WillAdd.Score = ValueArr[I];
            WillAdd.Weight = WeightArr[I];
            ItemInfoList.Add(WillAdd);
        }
        mItemInfoArr = ItemInfoList.ToArray();
        UB = mItemInfoArr.GetUpperBound(0);

        // スコア[重さ][どこまでみたか]なインラインDPのDict
        var DPArrDict1 = new Dictionary<long, long?[]>();
        DPArrDict1[UB] = new long?[mWeightLimit + 1];
        DPArrDict1[UB][0] = 0;

        // 最後に選んだ品物[重さ][どこまでみたか]なインラインDP表
        var DPArrDict2 = new Dictionary<long, long?[]>();
        DPArrDict2[UB] = new long?[mWeightLimit + 1];

        for (long I = UB; 0 <= I; I--) {
            long?[] CurrArr1 = DPArrDict1[I];
            long?[] CurrArr2 = DPArrDict2[I];
            for (long J = mWeightLimit; 0 <= J; J--) {
                if (CurrArr1[J].HasValue == false) continue;
                long NewJ = J + mItemInfoArr[I].Weight;
                if (NewJ > mWeightLimit) continue;

                long NewScore = CurrArr1[J].Value + mItemInfoArr[I].Score;

                if (CurrArr1[NewJ].HasValue) {
                    if (CurrArr1[NewJ].Value > NewScore) {
                        continue;
                    }
                    if (CurrArr1[NewJ].Value == NewScore) {
                        if (CurrArr2[NewJ].HasValue) {
                            if (CurrArr2[NewJ] > I) {
                                continue;
                            }
                        }
                    }
                }
                CurrArr1[NewJ] = NewScore;
                CurrArr2[NewJ] = I;
            }

            if (0 < I) {
                DPArrDict1[I - 1] = (long?[])DPArrDict1[I].Clone();
                DPArrDict2[I - 1] = (long?[])DPArrDict2[I].Clone();
            }
        }

        // ------------------------------------------------------
        // DPの復元を行う
        // ------------------------------------------------------
        long CurrInd = 0;
        long RestWeight = mWeightLimit;

        var AnswerList = new List<long>();
        while (true) {
            bool HasAnswer = false;
            long AnswerItem = -1;

            long MaxScore = long.MinValue;

            for (long I = 0; I <= RestWeight; I++) {
                long?[] CurrArr1 = DPArrDict1[CurrInd];
                long?[] CurrArr2 = DPArrDict2[CurrInd];
                if (CurrArr1[I].HasValue == false) continue;
                if (CurrArr1[I].Value == 0) continue;
                if (MaxScore > CurrArr1[I].Value) continue;

                if (MaxScore == CurrArr1[I]) {
                    if (AnswerItem > CurrArr2[I]) {
                        continue;
                    }
                }

                HasAnswer = true;
                MaxScore = CurrArr1[I].Value;
                AnswerItem = CurrArr2[I].Value;
            }

            if (HasAnswer == false) {
                break;
            }
            RestWeight -= mItemInfoArr[AnswerItem].Weight;
            AnswerList.Add(AnswerItem);

            CurrInd = AnswerItem + 1;
            if (CurrInd > UB) break;
        }

        Console.WriteLine(AnswerList.Count);

        for (int I = 0; I <= AnswerList.Count - 1; I++) {
            AnswerList[I]++;
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    // セパレータとLong型の列挙を引数として、結合したstringを返す
    static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

スコアが最大となる選び方の中で
辞書順で最大の選び方が解なので

[UB  ,UB]で最大スコアが達成可能なら、解の選び方で最初に選ぶものはUB
[UB-1,UB]で最大スコアが達成可能なら、解の選び方で最初に選ぶものはUB-1
[UB-2,UB]で最大スコアが達成可能なら、解の選び方で最初に選ぶものはUB-2
[UB-3,UB]で最大スコアが達成可能なら、解の選び方で最初に選ぶものはUB-3
[UB-4,UB]で最大スコアが達成可能なら、解の選び方で最初に選ぶものはUB-4
と分かります。

なので添え字の大きい順に見ていくこととしてます。

そして、DPの復元も考慮すると、状態は下記の2つを持てば良いです。

スコア[重さ][どこまでみたか]なインラインDPのDict
最後に選んだ品物[重さ][どこまでみたか]なインラインDPのDict
(重さは必ず増えるのでインラインDPにできます)

また、C#では、配列のCloneが高速なので、
定数倍対策で、配列のCloneが使えるようにDPの状態を持たせてます。

後は、
UBから0までDPし
解の選び方で、1番目が分かったら、
重さ制限を変えつつ、どこまでみたかも変更し
再帰的に解を求めることができます。