結果
問題 | No.27 板の準備 |
ユーザー | 明智重蔵 |
提出日時 | 2015-08-02 19:19:52 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,346 bytes |
コンパイル時間 | 2,430 ms |
コンパイル使用メモリ | 107,156 KB |
実行使用メモリ | 28,388 KB |
最終ジャッジ日時 | 2023-09-25 00:35:16 |
合計ジャッジ時間 | 7,788 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 71 ms
24,200 KB |
testcase_01 | AC | 71 ms
22,056 KB |
testcase_02 | AC | 95 ms
28,300 KB |
testcase_03 | AC | 72 ms
22,064 KB |
testcase_04 | AC | 142 ms
28,224 KB |
testcase_05 | AC | 166 ms
28,208 KB |
testcase_06 | AC | 412 ms
28,316 KB |
testcase_07 | AC | 441 ms
28,276 KB |
testcase_08 | AC | 986 ms
28,388 KB |
testcase_09 | AC | 683 ms
26,300 KB |
testcase_10 | AC | 241 ms
26,232 KB |
testcase_11 | AC | 164 ms
26,260 KB |
testcase_12 | AC | 227 ms
26,288 KB |
testcase_13 | AC | 111 ms
26,172 KB |
testcase_14 | AC | 91 ms
26,284 KB |
testcase_15 | AC | 177 ms
26,240 KB |
testcase_16 | WA | - |
testcase_17 | AC | 166 ms
26,176 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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); } } } }