結果

問題 No.27 板の準備
コンテスト
ユーザー 明智重蔵
提出日時 2015-08-02 19:19:52
言語 C#(csc)
(csc 3.9.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,346 bytes
コンパイル時間 1,086 ms
コンパイル使用メモリ 116,704 KB
実行使用メモリ 31,712 KB
最終ジャッジ日時 2024-07-18 00:49:18
合計ジャッジ時間 5,020 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;

    //No.27 板の準備
    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; B <= pMaxLen; B++) {
                for (int C = B; C <= pMaxLen; C++) {
                    var wkList = new int[] { A, B, C };
                    int[] WillAdd = wkList.Distinct().ToArray();
                    WillReturn.Add(WillAdd);
                }
            }
        }
        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