結果

問題 No.90 品物の並び替え
ユーザー Masahiro HayashiMasahiro Hayashi
提出日時 2014-12-25 22:08:25
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 2,229 ms / 5,000 ms
コード長 3,351 bytes
コンパイル時間 2,360 ms
コンパイル使用メモリ 117,136 KB
実行使用メモリ 31,380 KB
最終ジャッジ日時 2024-06-12 23:03:15
合計ジャッジ時間 6,063 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
25,140 KB
testcase_01 AC 237 ms
31,244 KB
testcase_02 AC 32 ms
25,012 KB
testcase_03 AC 54 ms
31,364 KB
testcase_04 AC 55 ms
27,148 KB
testcase_05 AC 236 ms
31,380 KB
testcase_06 AC 240 ms
31,236 KB
testcase_07 AC 34 ms
28,916 KB
testcase_08 AC 30 ms
25,136 KB
testcase_09 AC 2,229 ms
29,352 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