AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC403-D Forbidden Difference
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 2");
WillReturn.Add("3 1 4 1 5");
//1
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 3");
WillReturn.Add("1 6 1 8");
//0
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 3");
WillReturn.Add("1 6 2 10 2 3 2 10 6 4");
//2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long Diff = wkArr[1];
long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
var CntDict = new Dictionary<long, long>();
foreach (long EachA in AArr) {
if (CntDict.ContainsKey(EachA) == false) {
CntDict[EachA] = 0;
}
CntDict[EachA]++;
}
if (Diff == 0) {
long SpecialAns = 0;
foreach (var EachPair in CntDict) {
if (EachPair.Value >= 2) {
SpecialAns += EachPair.Value - 1;
}
}
Console.WriteLine(SpecialAns);
return;
}
long Answer = 0;
// コストのList[法]なDict
var CostListDict = new Dictionary<long, List<long>>();
foreach (var EachPair in CntDict.OrderBy(pX => pX.Key)) {
long Mod = EachPair.Key % Diff;
if (CostListDict.ContainsKey(Mod) == false) {
CostListDict[Mod] = new List<long>();
}
CostListDict[Mod].Add(EachPair.Value);
long NextVal = EachPair.Key + Diff;
if (CntDict.ContainsKey(NextVal) == false) {
long CurrAnswer = 0;
CurrAnswer = DeriveAnswer(CostListDict[Mod].ToArray());
Answer += CurrAnswer;
CostListDict[Mod].Clear();
}
}
Console.WriteLine(Answer);
}
// コストを返す
static long DeriveAnswer(long[] pCostArr)
{
// コスト[次がコスト必須か?]
long?[] PrevDP = new long?[2];
PrevDP[0] = 0;
foreach (long EachCost in pCostArr) {
long?[] CurrDP = new long?[2];
for (long I = 0; I <= 1; I++) {
if (PrevDP[I].HasValue == false) continue;
Action<long, long> UpdateAct = (pNewI, pNewVal) =>
{
if (CurrDP[pNewI].HasValue) {
if (CurrDP[pNewI] <= pNewVal) {
return;
}
}
CurrDP[pNewI] = pNewVal;
};
// コストとする場合
UpdateAct(0, PrevDP[I].Value + EachCost);
// コストとしない場合
if (I == 0) {
UpdateAct(1, PrevDP[I].Value);
}
}
PrevDP = CurrDP;
}
var AnswerList = new List<long>();
for (long I = 0; I <= 1; I++) {
if (PrevDP[I].HasValue) {
AnswerList.Add(PrevDP[I].Value);
}
}
return AnswerList.Min();
}
}
解説
まず、Diffが0かで場合分けします。
Diffが0なら重複を無くすコストが解になります。
Diffが0でなければ、Diffを法として、
連続したグループで、最小コスト[次がコスト必須か?]でDPします。
E8本(数学) 031 Taro's VacationがDPパートの類題です。