結果

問題 No.90 品物の並び替え
ユーザー Masahiro HayashiMasahiro Hayashi
提出日時 2014-12-25 22:08:25
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,040 ms / 5,000 ms
コード長 3,351 bytes
コンパイル時間 4,377 ms
コンパイル使用メモリ 110,888 KB
実行使用メモリ 27,948 KB
最終ジャッジ日時 2023-09-03 17:32:06
合計ジャッジ時間 7,664 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 54 ms
23,772 KB
testcase_01 AC 244 ms
27,840 KB
testcase_02 AC 58 ms
21,776 KB
testcase_03 AC 79 ms
27,904 KB
testcase_04 AC 77 ms
25,860 KB
testcase_05 AC 247 ms
27,924 KB
testcase_06 AC 249 ms
27,948 KB
testcase_07 AC 61 ms
25,864 KB
testcase_08 AC 57 ms
23,776 KB
testcase_09 AC 2,040 ms
26,256 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;
using System.Text;

namespace Application
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            var scan = new Scanner();

            var N = scan.NextDigit();
            var M = scan.NextDigit();
            var scores = new int[N, N];

            for (var i = 0; i < M; i++)
            {
                var line = scan.NextDigits(3);
                scores[line[0], line[1]] = line[2];
            }

            var result = computePrice(scores, N, M);

            WriteLine(result);
        }

        static int computePrice(int[,] scores, int N, int M)
        {
            return DepthFirstSearch(scores, Enumerable.Empty<int>(), Enumerable.Range(0, N));
        }

        static IEnumerable<T> Add<T>(IEnumerable<T> list, T item)
        {
            return list.Concat(Enumerable.Repeat(item, 1));
        }

        static IEnumerable<T> Remove<T>(IEnumerable<T> list, T item)
        {
            return list.Where(s => !s.Equals(item));
        }

        static int DepthFirstSearch(int[,] scores, IEnumerable<int> done, IEnumerable<int> left)
        {
            var max = 0;

            foreach (var i in left)
            {
                var doneScore = done.Aggregate(0, (memo, j) => memo + scores[j, i]);
                var childMax = DepthFirstSearch(scores, Add(done, i), Remove(left, i));

                max = Math.Max(doneScore + childMax, max);
            }

            return max;
        }

        static void WriteLine(object o)
        {
            System.Console.WriteLine(o.ToString());
        }

        static void D<T>(IEnumerable<T> l)
        {
            WriteLine(JoinList(l));
        }

        private static string JoinList<T>(IEnumerable<T> l)
        {
            return string.Join(" ", l.Select(x => x.ToString()).ToArray());
        }
    }

    class Scanner
    {
        public int[] NextDigits(int count)
        {
            return Enumerable.Range(0, count)
                .Select(x => NextDigit()).ToArray();
        }

        public string NextToken()
        {
            int i;
            var r = new List<char>();

            while ((i = System.Console.Read()) >= 0)
            {
                var c = Convert.ToChar(i);

                if (IsSpace(c) && r.Count > 0)
                    break;

                r.Add(c);
            }

            return new string(r.ToArray());
        }

        bool IsSpace(char c)
        {
            if (char.IsWhiteSpace(c)) return true;

            return false;
        }

        public int NextDigit()
        {
            var token = NextToken();

            return int.Parse(token);
        }
    }

    class Reader
    {
        public string Item()
        {
            return Items()[0];
        }

        public String[] Items()
        {
            return this.Items(' ');
        }

        public String[] Items(char c)
        {
            return System.Console.ReadLine().Split(c);
        }

        public int Int()
        {
            return Ints(' ')[0];
        }

        public int[] Ints()
        {
            return this.Ints(' ');
        }

        public int[] Ints(char c)
        {
            return Items(c).Select(x => int.Parse(x)).ToArray();
        }
    }
}
0