結果
問題 | No.90 品物の並び替え |
ユーザー | 明智重蔵 |
提出日時 | 2015-09-15 15:59:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,512 ms / 5,000 ms |
コード長 | 3,459 bytes |
コンパイル時間 | 2,647 ms |
コンパイル使用メモリ | 107,764 KB |
実行使用メモリ | 58,680 KB |
最終ジャッジ日時 | 2023-09-26 12:04:04 |
合計ジャッジ時間 | 7,450 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 70 ms
21,756 KB |
testcase_01 | AC | 279 ms
31,184 KB |
testcase_02 | AC | 70 ms
23,780 KB |
testcase_03 | AC | 90 ms
27,944 KB |
testcase_04 | AC | 96 ms
25,872 KB |
testcase_05 | AC | 293 ms
29,204 KB |
testcase_06 | AC | 261 ms
29,196 KB |
testcase_07 | AC | 74 ms
19,792 KB |
testcase_08 | AC | 71 ms
21,832 KB |
testcase_09 | AC | 2,512 ms
58,680 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 = "Input2"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("4 9"); WillReturn.Add("0 1 1"); WillReturn.Add("0 2 2"); WillReturn.Add("0 3 3"); WillReturn.Add("1 2 4"); WillReturn.Add("1 3 5"); WillReturn.Add("2 3 6"); WillReturn.Add("3 2 100"); WillReturn.Add("2 1 100"); WillReturn.Add("1 0 100"); //300 //3 2 1 0 //と並べた時の300点が最大となる。 //0 1 2 3 //と並べた時、適用される数は6個だが、21点となり、最高点は得られないことに注意せよ。 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct TokutenDef { internal int Item1; internal int Item2; internal int Score; } static void Main() { List<string> InputList = GetInputList(); int N = int.Parse(InputList[0].Split(' ').First()); int[] wkArr = { }; Action<string> SplitAct = pStr => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); var TokutenList = new List<TokutenDef>(); foreach (string EachStr in InputList.Skip(1)) { SplitAct(EachStr); TokutenList.Add(new TokutenDef() { Item1 = wkArr[0], Item2 = wkArr[1], Score = wkArr[2] }); } TokutenDef[] TokutenArr = TokutenList.ToArray(); List<int[]> NumArrList = ExecDFS(N); int MaxScoreSum = int.MinValue; foreach (int[] EachNumArr in NumArrList) { //数値ごとの存在する添字のDict var NumIndDict = new Dictionary<int, int>(); for (int I = 0; I <= EachNumArr.GetUpperBound(0); I++) { NumIndDict[EachNumArr[I]] = I; } int ScoreSum = 0; foreach (TokutenDef EachTokuten in TokutenArr) { if (NumIndDict[EachTokuten.Item1] < NumIndDict[EachTokuten.Item2]) ScoreSum += EachTokuten.Score; } if (MaxScoreSum < ScoreSum) MaxScoreSum = ScoreSum; } Console.WriteLine(MaxScoreSum); } struct JyoutaiDef { internal List<int> NumList; } //深さ優先探索で順列を列挙する static List<int[]> ExecDFS(int pN) { var WillReturn = new List<int[]>(); var stk = new Stack<JyoutaiDef>(); JyoutaiDef WillPush; for (int I = 0; I <= pN - 1; I++) { WillPush.NumList = new List<int> { I }; stk.Push(WillPush); } while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); if (Popped.NumList.Count == pN) { WillReturn.Add(Popped.NumList.ToArray()); continue; } for (int I = 0; I <= pN - 1; I++) { if (Popped.NumList.Contains(I)) continue; WillPush.NumList = new List<int>(Popped.NumList) { I }; stk.Push(WillPush); } } return WillReturn; } }