AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC236-F Spices
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("2");
WillReturn.Add("4 5 3");
//7
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("9 7 9 7 10 4 3 9 4 8 10 5 6 3 8");
//15
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct SpiceInfoDef
{
internal int Num;
internal int Cost;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
int N = int.Parse(InputList[0]);
int[] CArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
var SpiceInfoList = new List<SpiceInfoDef>();
for (int I = 0; I <= CArr.GetUpperBound(0); I++) {
SpiceInfoDef WillAdd;
WillAdd.Num = I + 1;
WillAdd.Cost = CArr[I];
SpiceInfoList.Add(WillAdd);
}
// コストの昇順にソート
SpiceInfoList = SpiceInfoList.OrderBy(pX => pX.Cost).ToList();
long Answer = 0;
var XORSet = new HashSet<int>();
foreach (SpiceInfoDef EachSpiceInfo in SpiceInfoList) {
if (XORSet.Contains(EachSpiceInfo.Num)) {
continue;
}
Answer += EachSpiceInfo.Cost;
XORSet.Add(EachSpiceInfo.Num);
foreach (int EachInt in XORSet.ToArray()) {
XORSet.Add(EachInt ^ EachSpiceInfo.Num);
}
}
Console.WriteLine(Answer);
}
}
解説
クラスカル法の感覚で、
コストの昇順に、遷移可能なノードを増やせるかをチェックしてます。