結果

問題 No.90 品物の並び替え
ユーザー Masahiro 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
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();
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0