#41286 (C#(csc)) No.15 カタログショッピング

提出ソース

結果

問題	No.15 カタログショッピング
ユーザー	明智重蔵
提出日時	2015-08-02 17:49:44
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	168 ms / 5,000 ms
コード長	10,807 bytes
コンパイル時間	957 ms
コンパイル使用メモリ	116,812 KB
実行使用メモリ	50,212 KB
最終ジャッジ日時	2024-07-18 00:48:47
合計ジャッジ時間	2,580 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	46 ms 26,104 KB
testcase_01	AC	46 ms 26,032 KB
testcase_02	AC	46 ms 25,992 KB
testcase_03	AC	47 ms 26,284 KB
testcase_04	AC	47 ms 25,872 KB
testcase_05	AC	163 ms 50,212 KB
testcase_06	AC	168 ms 46,380 KB
testcase_07	AC	165 ms 48,428 KB
testcase_08	AC	166 ms 48,552 KB
testcase_09	AC	164 ms 49,720 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

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

class Program
{
    static string InputPattern = "Input7";

    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");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 150");
            WillReturn.Add("10");
            WillReturn.Add("30");
            WillReturn.Add("40");
            WillReturn.Add("20");
            WillReturn.Add("50");
        }
        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
        }
        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
        }
        else if (InputPattern == "Input6") {
            WillReturn.Add("31 96298131");
            WillReturn.Add("1550570");
            WillReturn.Add("53201");
            WillReturn.Add("2661610");
            WillReturn.Add("846149");
            WillReturn.Add("1024350");
            WillReturn.Add("916520");
            WillReturn.Add("1608279");
            WillReturn.Add("8448655");
            WillReturn.Add("3425761");
            WillReturn.Add("4447092");
            WillReturn.Add("6304737");
            WillReturn.Add("9146858");
            WillReturn.Add("6943857");
            WillReturn.Add("5799811");
            WillReturn.Add("9355117");
            WillReturn.Add("1845095");
            WillReturn.Add("6125554");
            WillReturn.Add("2553406");
            WillReturn.Add("9587206");
            WillReturn.Add("4902519");
            WillReturn.Add("1490990");
            WillReturn.Add("4041027");
            WillReturn.Add("7434093");
            WillReturn.Add("2605431");
            WillReturn.Add("7672204");
            WillReturn.Add("5280869");
            WillReturn.Add("9418500");
            WillReturn.Add("277277");
            WillReturn.Add("933561");
            WillReturn.Add("3301324");
            WillReturn.Add("4067973");
        }

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

        //半分全探索の前半部と後半部を使って解判定を行う
        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());
        }
        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());
        }
    }

    //半分全探索の前半部と後半部を使って解判定を行う
    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());
        }
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード