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