結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー aketijyuuzou
提出日時 2025-12-17 19:50:47
言語 C#
(.NET 8.0.404)
結果
TLE  
実行時間 -
コード長 6,246 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,528 ms
コンパイル使用メモリ 171,408 KB
実行使用メモリ 365,704 KB
最終ジャッジ日時 2025-12-17 19:51:01
合計ジャッジ時間 13,371 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 68
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (103 ミリ秒)。
  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 ItemInfoDef[] mItemInfoArr;

    static long UB;
    static long mWeightLimit;


    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        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);

        // {スコア , 最後に選択したInd} [重さ]なインラインDP表
        var DPDict = new Dictionary<long, JyoutaiDef>();

        for (long I = UB; 0 <= I; I--) {
            var CurrUpdateInfoList = new List<UpdateInfoDef>();
            Action<long, long> UpdateAct = (pNewScore, pWeightSum) =>
            {
                if (pWeightSum > mWeightLimit) return;

                bool IsOK = false;
                if (DPDict.ContainsKey(pWeightSum)) {
                    if (DPDict[pWeightSum].Score < pNewScore) {
                        IsOK = true;
                    }
                    else if (DPDict[pWeightSum].Score == pNewScore) {
                        if (DPDict[pWeightSum].LastItemInd < I) {
                            IsOK = true;
                        }
                    }
                }
                else {
                    IsOK = true;
                }

                if (IsOK) {
                    UpdateInfoDef CurrUpdateInfo;
                    CurrUpdateInfo.Weight = pWeightSum;
                    CurrUpdateInfo.Score = pNewScore;
                    CurrUpdateInfo.LastItemInd = I;
                    CurrUpdateInfoList.Add(CurrUpdateInfo);
                }
            };

            foreach (var EachPair in DPDict) {
                UpdateAct(EachPair.Value.Score + mItemInfoArr[I].Score, EachPair.Key + mItemInfoArr[I].Weight);
            }

            UpdateAct(mItemInfoArr[I].Score, mItemInfoArr[I].Weight);

            foreach (UpdateInfoDef EachUpdateInfo in CurrUpdateInfoList) {
                DPDict[EachUpdateInfo.Weight] = new JyoutaiDef();
                DPDict[EachUpdateInfo.Weight].Score = EachUpdateInfo.Score;
                DPDict[EachUpdateInfo.Weight].LastItemInd = EachUpdateInfo.LastItemInd;
            }

            mUpdateInfoList.AddRange(CurrUpdateInfoList);
        }

        //foreach (UpdateInfoDef EachUpdateInfo in mUpdateInfoList) {
        //    Console.WriteLine("Weight={0},Score={1},LastItemInd={2}",
        //        EachUpdateInfo.Weight, EachUpdateInfo.Score, EachUpdateInfo.LastItemInd);
        //}

        ExecDP();
    }

    class JyoutaiDef
    {
        internal long Score;
        internal long LastItemInd;
    }

    // DPの更新情報
    struct UpdateInfoDef
    {
        internal long Weight;
        internal long Score;
        internal long LastItemInd;
    }
    static List<UpdateInfoDef> mUpdateInfoList = new List<UpdateInfoDef>();

    // DP復元を行う
    static void ExecDP()
    {
        var AnswerIndList = new List<long>();

        long CurrInd = 0;
        long CurrWeightLimit = mWeightLimit;
        while (true) {
            // RemoveAllで不要データの削除
            mUpdateInfoList.RemoveAll(pX => pX.Weight > CurrWeightLimit || pX.LastItemInd < CurrInd);

            // 定数倍改善でソートを定義できる構造体にする余地あり
            var Tmp1 = mUpdateInfoList.OrderByDescending(pX => pX.Score);
            var Tmp2 = Tmp1.ThenByDescending(pX => pX.LastItemInd);
            if (Tmp2.Any() == false) break;

            UpdateInfoDef CurrAnswer = Tmp2.First();
            AnswerIndList.Add(CurrAnswer.LastItemInd);
            CurrWeightLimit -= mItemInfoArr[CurrAnswer.LastItemInd].Weight;
            CurrInd = CurrAnswer.LastItemInd + 1;

            //Console.WriteLine("CurrWeightLimit={0},", CurrWeightLimit);
            //Console.WriteLine("CurrInd={0},", CurrInd);
        }

        Console.WriteLine(AnswerIndList.Count);
        for (int I = 0; I <= AnswerIndList.Count - 1; I++) {
            // 1オリジンに変更
            AnswerIndList[I]++;
        }
        Console.WriteLine(LongEnumJoin(" ", AnswerIndList));
    }

    // セパレータと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