ABC419-E Subarray Sum Divisibility

問題へのリンク

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("4 5 3");
            WillReturn.Add("4 2 1 3");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 10 4");
            WillReturn.Add("7 0 9 1 6 4 2");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mM;
    static long mL;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        mM = wkArr[1];
        mL = wkArr[2];

        long[] AArr = GetSplitArr(InputList[1]);
        long UB = AArr.GetUpperBound(0);

        for (long I = 0; I <= UB; I++) {
            AArr[I] %= mM;
        }

        // 値リスト[ind % (mL - 1)]なDict
        var ValListDict = new Dictionary<long, List<long>>();

        for (long I = 0; I <= UB; I++) {
            long KeyVal = I % mL;
            if (ValListDict.ContainsKey(KeyVal) == false) {
                ValListDict[KeyVal] = new List<long>();
            }
            ValListDict[KeyVal].Add(AArr[I]);
        }

        // 最小コスト[mod Mでの余り]なDP表
        long?[] PrevDP = new long?[mM];
        PrevDP[0] = 0;

        foreach (var EachPair in ValListDict) {
            List<long> ValList = EachPair.Value;

            long?[] CurrDP = new long?[mM];
            for (long I = 0; I <= mM - 1; I++) {
                if (PrevDP[I].HasValue == false) continue;

                // 設定する値でループ
                for (long LoopCurrAmari = 0; LoopCurrAmari <= mM - 1; LoopCurrAmari++) {
                    long NewI = (I + LoopCurrAmari) % mM;
                    long NewVal = PrevDP[I].Value + DeriveCost(ValList, LoopCurrAmari);

                    if (CurrDP[NewI].HasValue) {
                        if (CurrDP[NewI] <= NewVal) {
                            continue;
                        }
                    }
                    CurrDP[NewI] = NewVal;
                }
            }
            PrevDP = CurrDP;
        }

        Console.WriteLine(PrevDP[0]);
    }

    // 値リストと余りを引数とし、コストを返す
    static long DeriveCost(List<long> pList, long pGoalAmari)
    {
        long Cost = 0;
        foreach (long EachVal in pList) {
            if (EachVal <= pGoalAmari) {
                Cost += pGoalAmari - EachVal;
            }
            else {
                Cost += (pGoalAmari + mM) - EachVal;
            }
        }
        return Cost;
    }
}

解説

長さは3 法は9
数列は、
A B C D E F G H I
として考えます。

   A + B + C ≡ B + C + D
⇔         A ≡ D

   B + C + D ≡ C + D + E
⇔         B ≡ E

   C + D + E ≡ D + E + F
⇔         C ≡ F

より、3つ先は、必ずmodの世界で等しいと分かります。

また、
数列の最初のL項の総和がmod Mで0であれば
どの長さLの部分列もmod Mで0だと分かります。

なので、
数列の最初のL項に着目し、
最小コスト[mod Mでの余り]でDPすれば良いです。

DPの際にコストを計算しやすいように、
A B C D E F G H I
から
A -> D -> G
B -> E -> H
C -> F -> I
という3つのListを準備してます。