AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC255-E Lucky Numbers
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("9 2");
WillReturn.Add("2 3 3 4 -4 -7 -4 -1");
WillReturn.Add("-1 5");
//4
}
else if (InputPattern == "Input2") {
WillReturn.Add("20 10");
WillReturn.Add("-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901");
WillReturn.Add("-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398");
//8
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] SArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] XArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
// スコア[初項]なDict
var CntDict = new Dictionary<long, long>();
foreach (long EachX in XArr) {
if (CntDict.ContainsKey(EachX) == false) {
CntDict[EachX] = 0;
}
CntDict[EachX]++;
}
long OddSum = 0;
long EvenSum = 0;
for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
if (I % 2 == 0) EvenSum += SArr[I];
if (I % 2 == 1) OddSum += SArr[I];
foreach (long EachX in XArr) {
long Syokou = -EachX - OddSum + EvenSum;
if (I % 2 == 1) {
Syokou = EachX - OddSum + EvenSum;
}
if (CntDict.ContainsKey(Syokou) == false) {
CntDict[Syokou] = 0;
}
CntDict[Syokou]++;
}
}
Console.WriteLine(CntDict.Values.Max());
}
}
解説
初項が決まれば、数列が決定するので、
初項を数列のハッシュ値として、
初項ごとのスコアを集計してます。
以下の連立方程式から
V1 + V2 = S1
V2 + V3 = S2
V3 + V4 = S3
V4 + V5 = S4
V5 + V6 = S5
下記が導出できることもふまえてます。
V1 = S1-V2
V1 = S1-S2+V3
V1 = S1-S2+S3-V4
V1 = S1-S2+S3-S4+V5
V1 = S1-S2+S3-S4+S5-V6