結果

問題 No.27 板の準備
ユーザー 明智重蔵明智重蔵
提出日時 2015-08-02 19:07:00
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,222 bytes
コンパイル時間 1,032 ms
コンパイル使用メモリ 114,676 KB
実行使用メモリ 31,664 KB
最終ジャッジ日時 2024-07-18 00:49:10
合計ジャッジ時間 5,442 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 33 ms
23,472 KB
testcase_02 AC 52 ms
31,320 KB
testcase_03 AC 34 ms
27,256 KB
testcase_04 AC 98 ms
29,500 KB
testcase_05 AC 120 ms
27,448 KB
testcase_06 AC 351 ms
31,572 KB
testcase_07 AC 379 ms
29,780 KB
testcase_08 AC 950 ms
29,576 KB
testcase_09 AC 617 ms
27,788 KB
testcase_10 AC 197 ms
29,280 KB
testcase_11 AC 120 ms
31,528 KB
testcase_12 AC 182 ms
31,580 KB
testcase_13 AC 68 ms
31,524 KB
testcase_14 AC 52 ms
31,664 KB
testcase_15 AC 137 ms
31,304 KB
testcase_16 WA -
testcase_17 AC 119 ms
27,420 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = "Input4";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("28 29 30 30");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 3 7 15");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 6 11 20");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    //必要な板の長さの配列
    static int[] NeedLenArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        NeedLenArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();
        List<int[]> LenCombiArrList = DeriveLenCombiArrList(NeedLenArr.Max());


        int AnswerCnt = int.MaxValue;
        string AnswerItaCombi = "";
        string AnswerLog = "";
        foreach (int[] EachCombiArr in LenCombiArrList) {
            bool FoundAnswer;
            int MinItaCnt;
            string Log;

            DeriveNeedMinCnt(EachCombiArr, out FoundAnswer, out MinItaCnt, out Log);
            if (FoundAnswer == false) continue;
            if (AnswerCnt < MinItaCnt) continue;
            AnswerCnt = MinItaCnt;
            AnswerLog = Log;
            AnswerItaCombi = "";
            Array.ForEach(EachCombiArr, X => AnswerItaCombi += X.ToString() + ",");
        }
        Console.WriteLine(AnswerCnt);
        //Console.WriteLine("ABCの板の長さは{0}", AnswerItaCombi);
        //Console.WriteLine(AnswerLog);
    }

    //長さの組み合わせを求める
    static List<int[]> DeriveLenCombiArrList(int pMaxLen)
    {
        var WillReturn = new List<int[]>();

        for (int A = 1; A <= pMaxLen; A++) {
            for (int B = A + 1; B <= pMaxLen; B++) {
                for (int C = B + 1; C <= pMaxLen; C++) {
                    WillReturn.Add(new int[] { A, B, C });
                }
            }
        }
        return WillReturn;
    }

    struct JyoutaiDef
    {
        internal int CurrNeedLenP;
        internal int CurrItaP;
        internal int SumLen;
        internal int ItaCnt;
        internal string Log;
    }

    //4つの長さを満たす最小の板の枚数を深さ優先探索で求める
    static void DeriveNeedMinCnt(int[] pLenCombiArr, out bool pFoundAnswer,
                                 out int pMinItaCnt, out string pLog)
    {
        pFoundAnswer = false;
        pMinItaCnt = int.MaxValue;
        pLog = "";

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNeedLenP = 0;
        WillPush.CurrItaP = 0;
        WillPush.SumLen = 0;
        WillPush.ItaCnt = 0;
        WillPush.Log = "";
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.SumLen == NeedLenArr[Popped.CurrNeedLenP]) {
                Popped.CurrNeedLenP++;
                if (Popped.CurrNeedLenP > NeedLenArr.GetUpperBound(0)) {
                    pFoundAnswer = true;
                    if (pMinItaCnt > Popped.ItaCnt) {
                        pMinItaCnt = Popped.ItaCnt;
                        pLog = Popped.Log;
                    }
                    continue;
                }
                Popped.CurrItaP = 0;
                Popped.SumLen = 0;
            }

            WillPush.ItaCnt = Popped.ItaCnt + 1;
            if (WillPush.ItaCnt + 1 >= pMinItaCnt) continue;

            for (int I = Popped.CurrItaP; I <= pLenCombiArr.GetUpperBound(0); I++) {
                WillPush.CurrNeedLenP = Popped.CurrNeedLenP;
                WillPush.CurrItaP = I;

                WillPush.SumLen = Popped.SumLen + pLenCombiArr[I];
                if (WillPush.SumLen > NeedLenArr[Popped.CurrNeedLenP]) continue;

                WillPush.Log = Popped.Log +
                    string.Format("長さ{0}の板。", pLenCombiArr[I]);
                stk.Push(WillPush);
            }
        }
    }
}
0