結果

問題 No.15 カタログショッピング
コンテスト
ユーザー aketijyuuzou
提出日時 2024-10-10 21:29:55
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 161 ms / 5,000 ms
コード長 10,262 bytes
コンパイル時間 1,033 ms
コンパイル使用メモリ 119,232 KB
実行使用メモリ 50,384 KB
最終ジャッジ日時 2024-10-10 21:29:58
合計ジャッジ時間 2,696 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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("3 220");
            WillReturn.Add("180");
            WillReturn.Add("220");
            WillReturn.Add("280");
            //2
            //太郎君は3つの商品の中から、2番の商品だけを購入しました
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 150");
            WillReturn.Add("10");
            WillReturn.Add("30");
            WillReturn.Add("40");
            WillReturn.Add("20");
            WillReturn.Add("50");
            //1 2 3 4 5
            //太郎君は5つの商品をすべて購入しました
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("12 348940");
            WillReturn.Add("47250");
            WillReturn.Add("76500");
            WillReturn.Add("9520");
            WillReturn.Add("29960");
            WillReturn.Add("19520");
            WillReturn.Add("70960");
            WillReturn.Add("91390");
            WillReturn.Add("35610");
            WillReturn.Add("71190");
            WillReturn.Add("25840");
            WillReturn.Add("10150");
            WillReturn.Add("35000");
            //2 3 4 6 7 8 12
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("15 445566");
            WillReturn.Add("13075");
            WillReturn.Add("16966");
            WillReturn.Add("20695");
            WillReturn.Add("21052");
            WillReturn.Add("25917");
            WillReturn.Add("25917");
            WillReturn.Add("28431");
            WillReturn.Add("31001");
            WillReturn.Add("44064");
            WillReturn.Add("47151");
            WillReturn.Add("59372");
            WillReturn.Add("63934");
            WillReturn.Add("63934");
            WillReturn.Add("66757");
            WillReturn.Add("88888");
            //4 5 7 9 10 11 12 14 15
            //4 5 7 9 10 11 13 14 15
            //4 6 7 9 10 11 12 14 15
            //4 6 7 9 10 11 13 14 15
            //同じ値段の商品が複数存在する場合があります。
            //あり得る4つの組み合わせを、昇順に出力してください。
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("4 20000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
            WillReturn.Add("10000");
            //1 2
            //1 3
            //1 4
            //2 3
            //2 4
            //3 4
            //すべて同じ値段なので、どれか2つを購入したようです。
            //あり得る6つの組み合わせをすべて出力してください。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrP;
        internal int SumPrice;
        internal List<int> SelectedIDList;
    }

    struct SyouhinDef
    {
        internal int ID;
        internal int Price;
    }

    static int S;

    static void Main()
    {
        List<string> InputList = GetInputList();
        S = int.Parse(InputList[0].Split(' ').Last());

        var SyouhinList = new List<SyouhinDef>();
        int wkID = 1;
        foreach (string EachStr in InputList.Skip(1)) {
            SyouhinDef WillAdd;
            WillAdd.ID = wkID++;
            WillAdd.Price = int.Parse(EachStr);
            SyouhinList.Add(WillAdd);
        }

        //合計金額より価格の高い商品をRemove
        SyouhinList.RemoveAll(X => X.Price > S);

        //価格の昇順の配列に変換しておく
        SyouhinDef[] SyouhinArr =
            SyouhinList.OrderBy(X => X.Price).ThenBy(X => X.ID).ToArray();

        //半分全探索を行う
        JyoutaiDef[] JyoutaiArrZenhan = { };
        JyoutaiDef[] JyoutaiArrKouhan = { };
        int UB = SyouhinArr.GetUpperBound(0);
        int HalfUB = UB / 2;
        if (0 < HalfUB && HalfUB < UB) {
            JyoutaiArrZenhan = ExecHanbunZentansaku(SyouhinArr, 0, HalfUB);
            JyoutaiArrKouhan = ExecHanbunZentansaku(SyouhinArr, HalfUB + 1, UB);
        }
        else {
            JyoutaiArrZenhan = ExecHanbunZentansaku(SyouhinArr, 0, UB);
        }

        //デバッグ用で半分全探索の結果を出力
        //ProntResultHanbunZentansaku(JyoutaiArrZenhan, JyoutaiArrKouhan);

        //半分全探索の前半部と後半部を使って解判定を行う
        AnswerHantei(JyoutaiArrZenhan, JyoutaiArrKouhan);
    }

    //半分全探索を行う
    static JyoutaiDef[] ExecHanbunZentansaku(SyouhinDef[] pSyouhinArr, int pStaInd, int pEndInd)
    {
        var WillReturn = new List<JyoutaiDef>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        for (int I = pStaInd; I <= pEndInd; I++) {
            WillPush.CurrP = I;
            WillPush.SelectedIDList = new List<int>() { pSyouhinArr[I].ID };
            WillPush.SumPrice = pSyouhinArr[I].Price;
            stk.Push(WillPush);
        }

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();
            WillReturn.Add(Popped);

            for (int I = Popped.CurrP + 1; I <= pEndInd; I++) {
                WillPush.CurrP = I;
                WillPush.SumPrice = Popped.SumPrice + pSyouhinArr[I].Price;

                //合計金額を超えるならbreak
                if (S < WillPush.SumPrice) break;

                WillPush.SelectedIDList = new List<int>(Popped.SelectedIDList);
                WillPush.SelectedIDList.Add(pSyouhinArr[I].ID);

                stk.Push(WillPush);
            }
        }
        return WillReturn.ToArray();
    }

    //デバッグ用で半分全探索の結果を出力
    static void ProntResultHanbunZentansaku(JyoutaiDef[] pJyoutaiArrZenhan, JyoutaiDef[] pJyoutaiArrKouhan)
    {
        Console.WriteLine("■■■前半部■■■");
        for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("SumPrice={0}", pJyoutaiArrZenhan[I].SumPrice);
            sb.Append("  IDList=");
            foreach (int EachInt in pJyoutaiArrZenhan[I].SelectedIDList) {
                sb.AppendFormat("{0},", EachInt);
            }
            Console.WriteLine(sb.ToString());
        }
        if (pJyoutaiArrKouhan.Length > 0) Console.WriteLine("■■■後半部■■■");
        for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
            var sb = new System.Text.StringBuilder();
            sb.AppendFormat("SumPrice={0}", pJyoutaiArrKouhan[I].SumPrice);
            sb.Append("  IDList=");
            foreach (int EachInt in pJyoutaiArrKouhan[I].SelectedIDList) {
                sb.AppendFormat("{0},", EachInt);
            }
            Console.WriteLine(sb.ToString());
        }
        Console.WriteLine();
    }

    //半分全探索の前半部と後半部を使って解判定を行う
    static void AnswerHantei(JyoutaiDef[] pJyoutaiArrZenhan, JyoutaiDef[] pJyoutaiArrKouhan)
    {
        //価格の合計の昇順にソートしておく
        Array.Sort(pJyoutaiArrZenhan, (A, B) => A.SumPrice - B.SumPrice);
        Array.Sort(pJyoutaiArrKouhan, (A, B) => A.SumPrice - B.SumPrice);

        var AnswerList = new List<int[]>();

        //前半部だけで解だった場合
        for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
            if (pJyoutaiArrZenhan[I].SumPrice == S)
                AnswerList.Add(pJyoutaiArrZenhan[I].SelectedIDList.OrderBy(X => X).ToArray());
        }
        //後半部だけで解だった場合
        for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
            if (pJyoutaiArrKouhan[I].SumPrice == S)
                AnswerList.Add(pJyoutaiArrKouhan[I].SelectedIDList.OrderBy(X => X).ToArray());
        }

        //後半部のSumPriceごとの開始IndのDict
        var StartIndDict = new Dictionary<int, int>();
        for (int I = 0; I <= pJyoutaiArrKouhan.GetUpperBound(0); I++) {
            int wkSum = pJyoutaiArrKouhan[I].SumPrice;
            if (StartIndDict.ContainsKey(wkSum)) continue;
            StartIndDict[wkSum] = I;
        }

        for (int I = 0; I <= pJyoutaiArrZenhan.GetUpperBound(0); I++) {
            int NeedSum = S - pJyoutaiArrZenhan[I].SumPrice;
            if (StartIndDict.ContainsKey(NeedSum) == false) continue;

            int StartInd = StartIndDict[NeedSum];

            for (int J = StartInd; J <= pJyoutaiArrKouhan.GetUpperBound(0); J++) {
                int wkSum = pJyoutaiArrZenhan[I].SumPrice + pJyoutaiArrKouhan[J].SumPrice;
                if (wkSum > S) break;
                if (wkSum < S) continue;

                var wkList = new List<int>();
                wkList.AddRange(pJyoutaiArrZenhan[I].SelectedIDList);
                wkList.AddRange(pJyoutaiArrKouhan[J].SelectedIDList);
                wkList.Sort();
                AnswerList.Add(wkList.ToArray());
            }
        }
        PrintAnswer(AnswerList);
    }

    //解を出力
    static void PrintAnswer(List<int[]> pAnswerList)
    {
        pAnswerList.Sort((A, B) =>
        {
            int MaxUB = Math.Max(A.GetUpperBound(0), B.GetUpperBound(0));
            for (int I = 0; I <= MaxUB; I++) {
                if (I > A.GetUpperBound(0)) return -1;
                if (I > B.GetUpperBound(0)) return 1;
                if (A[I] > B[I]) return 1;
                if (A[I] < B[I]) return -1;
            }
            return 0;
        });

        foreach (int[] EachIntArr in pAnswerList) {
            var sb = new System.Text.StringBuilder();
            for (int I = 0; I <= EachIntArr.GetUpperBound(0); I++) {
                sb.Append(EachIntArr[I]);
                if (I < EachIntArr.GetUpperBound(0))
                    sb.Append(' ');
            }
            Console.WriteLine(sb.ToString());
        }
    }
}
0