ABC-037-C 総和

■■■問題■■■

長さNの数列 {ai} と1以上N以下の整数Kが与えられます。
この数列には長さKの連続する部分列が N-K+1 個あります。
これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。

■■■入力■■■

N K
a1 ・・・ aN

●1 <= K <= N <= 10万
●0 <= ai <= 1億
●ai は整数である。

■■■出力■■■

部分列に含まれる値の合計 N-K+1 個の総和を出力せよ。

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 3");
            WillReturn.Add("1 2 4 8 16");
            //49
            //(1+2+4)+(2+4+8)+(4+8+16)=49 なので、答えは 49 です。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20 10");
            string wkStr = "100000000 100000000 98667799 100000000 100000000 ";
            wkStr += "100000000 100000000 99986657 100000000 100000000 ";
            wkStr += "100000000 100000000 100000000 98995577 100000000 ";
            wkStr += "100000000 99999876 100000000 100000000 99999999";
            WillReturn.Add(wkStr);
            //10988865195
            //オーバーフローに注意してください
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => long.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        long N = wkArr[0];
        long K = wkArr[1];

        SplitAct(InputList[1]);
        long[] AArr = (long[])wkArr.Clone();

        Solve1(N, K, AArr);
        //Solve2(N, K, AArr);
    }

    //解法1 尺取法
    static void Solve1(long pN, long pK, long[] pAArr)
    {
        long UB = pAArr.GetUpperBound(0);

        long L = 0;
        long R = pK - 1;

        long CurrKSum = 0;
        for (long I = L; I <= R; I++) {
            CurrKSum += pAArr[I];
        }
        long Answer = CurrKSum;

        while (true) {
            L++; R++;
            if (R > UB) break;

            CurrKSum -= pAArr[L - 1];
            CurrKSum += pAArr[R];
            Answer += CurrKSum;
        }
        Console.WriteLine(Answer);
    }

    //解法2 累積和
    static void Solve2(long pN, long pK, long[] pAArr)
    {
        long Answer = 0;

        long UB = pAArr.GetUpperBound(0);
        long[] RumSumArr = new long[UB + 1];

        for (long I = 0; I <= UB; I++) {
            if (I == 0) RumSumArr[0] = pAArr[I];
            else RumSumArr[I] = RumSumArr[I - 1] + pAArr[I];

            if (I == pK - 1) Answer = RumSumArr[I];
            else if (I > pK - 1) Answer += RumSumArr[I] - RumSumArr[I - pK];
        }
        Console.WriteLine(Answer);
    }
}

解説

尺取法と累積和の2通りの方法で解いてます。