using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input4"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("10 9 3"); //1 2 6 //ルールを満たすおかしの組み合わせは //(1円,2円,6円) //(1円,3円,5円) //(2円,3円,4円) //の3つがありますが、 //このうち辞書順が最小になる(1円,2円,6円)の組み合わせが答えになります。 } else if (InputPattern == "Input2") { WillReturn.Add("10 9 4"); //-1 //残念ながら直樹くんはおかしを買うことができませんでした・・・ } else if (InputPattern == "Input3") { WillReturn.Add("30 40 4"); //1 2 7 30 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int CurrN; internal List SelectedList; internal int SumVal; } //メモ化探索用 struct MemoDef { internal int CurrN; internal int SelectedCnt; internal int SumVal; } //No.115 遠足のおやつ static void Main() { List InputList = GetInputList(); int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray(); int N = wkArr[0]; int D = wkArr[1]; int K = wkArr[2]; var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrN = 1; WillPush.SelectedList = new List(); WillPush.SumVal = 0; stk.Push(WillPush); var MemoList = new List(); while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //クリア判定 if (Popped.SelectedList.Count == K) { if (Popped.SumVal == D) { Console.WriteLine( string.Join(" ", Popped.SelectedList.Select(X => X.ToString()).ToArray())); return; } continue; } for (int I = N; Popped.CurrN <= I; I--) { WillPush.CurrN = I + 1; WillPush.SelectedList = new List(Popped.SelectedList) { I }; WillPush.SumVal = Popped.SumVal + I; //解でないのに半分を超えたら枝切り if (WillPush.SumVal != D && WillPush.SumVal > D / 2) { continue; } //メモ化探索 MemoDef MemoInfo; MemoInfo.CurrN = WillPush.CurrN; MemoInfo.SelectedCnt = WillPush.SelectedList.Count; MemoInfo.SumVal = WillPush.SumVal; if (MemoList.Exists(X => X.CurrN == MemoInfo.CurrN && X.SelectedCnt == MemoInfo.SelectedCnt && X.SumVal == MemoInfo.SumVal)) continue; MemoList.Add(MemoInfo); stk.Push(WillPush); } } } }