結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー aketijyuuzou
提出日時 2025-12-13 10:49:35
言語 C#
(.NET 8.0.404)
結果
TLE  
実行時間 -
コード長 5,030 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 8,742 ms
コンパイル使用メモリ 168,392 KB
実行使用メモリ 58,076 KB
最終ジャッジ日時 2025-12-13 10:50:59
合計ジャッジ時間 84,060 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 WA * 36 TLE * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (119 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
raw source code 

using System;
using System.Collections.Generic;
using System.Linq;

// No.3329 Only the Rightest Choice is Right!!!
// https://yukicoder.me/problems/no/3329
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 void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long WeightLimit = 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);
        }
        ItemInfoDef[] ItemInfoArr = ItemInfoList.ToArray();
        long UB = ItemInfoArr.GetUpperBound(0);


        // 状態[重さ]なインラインDP表
        var DPDict = new Dictionary<long, JyoutaiDef>();

        for (long I = UB; 0 <= I; I--) {
            Action<JyoutaiDef, long> UpdateAct = (pNewJyoutai, pNewWeight) =>
            {
                if (WeightLimit < pNewWeight) return;

                if (DPDict.ContainsKey(pNewWeight)) {
                    // スコアで劣る場合
                    if (DPDict[pNewWeight].Score > pNewJyoutai.Score) return;

                    // 現在ItemIndで劣る場合
                    if (DPDict[pNewWeight].CurrItemInd > pNewJyoutai.CurrItemInd) return;
                }
                DPDict[pNewWeight] = pNewJyoutai;
            };

            foreach (long EachKey in DPDict.Keys.ToArray().OrderByDescending(pX => pX)) {
                long NewWeight = EachKey + ItemInfoArr[I].Weight;
                if (NewWeight > WeightLimit) continue;

                JyoutaiDef CurrJyoutai = DPDict[EachKey];

                JyoutaiDef NewJyoutai;
                NewJyoutai.Score = CurrJyoutai.Score + ItemInfoArr[I].Score;
                NewJyoutai.CurrItemInd = I;
                NewJyoutai.PrevWeight = EachKey;
                UpdateAct(NewJyoutai, NewWeight);
            }

            // 1つ目として取得する場合
            JyoutaiDef FirstJyoutai;
            FirstJyoutai.Score = ItemInfoArr[I].Score;
            FirstJyoutai.CurrItemInd = I;
            FirstJyoutai.PrevWeight = -1;
            UpdateAct(FirstJyoutai, ItemInfoArr[I].Weight);
        }

        //foreach (var EachPair in DPDict.OrderBy(pX => pX.Key)) {
        //    Console.WriteLine("Weight={0},Score={1},CurrItemInd={2},PrevWeight={3}",
        //        EachPair.Key, EachPair.Value.Score, EachPair.Value.CurrItemInd, EachPair.Value.PrevWeight);
        //}

        // ----------------------------------------------------
        // DPの復元パート
        // ----------------------------------------------------
        var Tmp1 = DPDict.OrderByDescending(pX => pX.Value.Score);
        var Tmp2 = Tmp1.ThenByDescending(pX => pX.Value.CurrItemInd);
        long CurrWeight = Tmp2.First().Key;

        var AnswerList = new List<long>();
        while (true) {
            AnswerList.Add(1 + DPDict[CurrWeight].CurrItemInd);

            if (DPDict[CurrWeight].PrevWeight == -1) break;
            CurrWeight = DPDict[CurrWeight].PrevWeight;
        }
        Console.WriteLine(AnswerList.Count);
        Console.WriteLine(LongEnumJoin(" ", AnswerList));
    }

    struct JyoutaiDef
    {
        internal long Score;
        internal long CurrItemInd;
        internal long PrevWeight;
    }

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