AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC159-D Banned K
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("5");
WillReturn.Add("1 1 2 1 2");
//2
//2
//3
//2
//3
}
else if (InputPattern == "Input2") {
WillReturn.Add("4");
WillReturn.Add("1 2 3 4");
//0
//0
//0
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("5");
WillReturn.Add("3 3 3 3 3");
//6
//6
//6
//6
//6
}
else if (InputPattern == "Input4") {
WillReturn.Add("8");
WillReturn.Add("1 2 1 4 2 1 4 1");
//5
//7
//5
//7
//7
//5
//7
//5
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
// 数値ごとの件数を求める
var CntDict = AArr.GroupBy(pX => pX).ToDictionary(pX => pX.Key, pX => pX.Count());
long PatternSum = 0;
foreach (var EachPair in CntDict) {
if (EachPair.Value >= 2) {
PatternSum += DeriveCombi(EachPair.Value, 2);
}
}
for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
long MinusPatternCnt = CntDict[AArr[I]] - 1;
Console.WriteLine(PatternSum - MinusPatternCnt);
}
}
//nCrを求める
static long DeriveCombi(long pN, long pR)
{
long WillReturn = 1;
pR = Math.Min(pR, pN - pR);
var DivList = new List<long>();
for (long I = 2; I <= pR; I++) {
DivList.Add(I);
}
for (long I = pN - pR + 1; I <= pN; I++) {
WillReturn *= I;
for (int J = DivList.Count - 1; 0 <= J; J--) {
if (WillReturn % DivList[J] == 0) {
WillReturn /= DivList[J];
DivList.RemoveAt(J);
}
}
}
return WillReturn;
}
}
解説
最初に、同じ色を2つ取る場合の数を求めます。
次に、それぞれのボールをBanするので、
Banするボールを必ず選択して、同じ色を2つ取る場合の数を求め、
引き算してます。