Created
December 7, 2013 15:29
-
-
Save nakaji/7843916 to your computer and use it in GitHub Desktop.
paizaオンラインハッカソンVol.1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment