paizaオンラインハッカソンVol.1

ECCampaign.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace ECCampaign
{
    class Program
    {
        static void Main(string[] args)
        {
            //先頭行の解析（商品の総数とキャンペーンの日数）
            var parameters = Console.ReadLine().Split(new string[] { " ", "//" }, StringSplitOptions.None);
            var N = Int32.Parse(parameters[0].Trim());
            var D = Int32.Parse(parameters[1].Trim());

            // 商品の読み込み
            var itemList = new ItemList();
            for (var i = 0; i < N; i++)
            {
                var input = Console.ReadLine().Split(new string[] { " ", "//" }, StringSplitOptions.None);
                var price = Int32.Parse(input[0].Trim());
                itemList.Add(price);
            }

            // キャンペーン金額の読み込み
            var canpaignPrices = new List<int>();
            for (var i = 0; i < D; i++)
            {
                var input = Console.ReadLine().Split(new string[] { " ", "//" }, StringSplitOptions.None);
                var maxPrice = Int32.Parse(input[0].Trim());
                canpaignPrices.Add(maxPrice);
            }

            // 回答の作成
            var answer = new List<int>();
            canpaignPrices.ForEach(canpaignPrice =>
                                   {
                                       answer.Add(Canpaign.GetFreePrice(itemList, canpaignPrice));

                                   });
            answer.ForEach(x => Console.WriteLine(x));
        }
    }

    public class ItemList
    {
        private List<int> itemList = new List<int>();
        private Dictionary<int, int> priceDic = new Dictionary<int, int>();

        public void Add(int price)
        {
            //キャンペーン設定金額が1000000以下なので、(1000000-10)より高いの商品は無意味
            if (price > 1000000 - 10) return;

            int count;
            priceDic.TryGetValue(price, out count);
            if (count == 2) return; //同じ価格が既に2つ登録されている場合はペア金額の組み合わせは満足しているので無視

            itemList.Add(price);
            if (count == 0)
            {
                priceDic.Add(price, 1);
            }
            else
            {
                priceDic[price] = 2;
            }
        }

        public List<int> ToList()
        {
            return itemList;
        }
    }

    public static class Pairing
    {
        /// <summary>
        /// 商品毎にキャンペーン価格を満たす最大の組み合せ合計金額を計算したリストを返す
        /// </summary>
        /// <param name="itemList">商品リスト</param>
        /// <param name="canpaignPrice">キャンペーン価格</param>
        /// <returns>最大の組み合わせ金額リスト</returns>
        public static List<int> GetPairList(ItemList itemList, int canpaignPrice)
        {
            var pairList = new List<int>();
            var firstList = itemList.ToList().Where(x => x < canpaignPrice);
            var index = 0;
            foreach (var x in firstList)
            {
                int i = index++;
                int firstPrice = x;

                // 組み合わせ相手のリスト
                var secondList = firstList.ToList();
                secondList.RemoveRange(0, i + 1);

                var list = secondList.Where(y => y <= canpaignPrice - firstPrice);
                if (!list.Any()) continue;

                var maxPrice = firstPrice + list.Max();
                //キャンペーン価格そのものになった場合
                if (maxPrice == canpaignPrice)
                {
                    pairList.Clear();
                    pairList.Add(maxPrice);
                    break;
                }
                pairList.Add(maxPrice);
            }

            return pairList;
        }
    }

    public static class Canpaign
    {
        /// <summary>
        /// 無料になる組み合わせ金額を返す
        /// </summary>
        /// <param name="itemList">商品リスト</param>
        /// <param name="canpaignPrice">キャンペーン価格</param>
        /// <returns>無料になる組み合わせ金額</returns>
        public static int GetFreePrice(ItemList itemList, int canpaignPrice)
        {
            var pairs = Pairing.GetPairList(itemList, canpaignPrice);

            if (!pairs.Any()) return 0;

            return pairs.Max();
        }
    }
}