ABC265-D Iroha and Haiku (New ABC Edition)

問題へのリンク

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("10 5 7 5");
            WillReturn.Add("1 3 2 2 2 3 1 4 3 2");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9 100 101 100");
            WillReturn.Add("31 41 59 26 53 58 97 93 23");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7 1 1 1");
            WillReturn.Add("1 1 1 1 1 1 1");
            //Yes
        }
        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 P = wkArr[1];
        long Q = wkArr[2];
        long R = wkArr[3];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long[] RunSum = (long[])AArr.Clone();
        long UB = AArr.GetUpperBound(0);

        for (long I = 1; I <= UB; I++) {
            RunSum[I] += RunSum[I - 1];
        }

        long HitCnt = 0;

        long CurrInd = 0;
        while (CurrInd <= UB) {
            long SearchVal = 0;
            if (HitCnt == 0) SearchVal = P;
            if (HitCnt == 1) SearchVal = Q;
            if (HitCnt == 2) SearchVal = R;
            if (CurrInd > 0) {
                SearchVal += RunSum[CurrInd - 1];
            }

            long ResultInd = Array.BinarySearch(RunSum, SearchVal);

            if (ResultInd >= 0) {
                if (++HitCnt == 3) {
                    Console.WriteLine("Yes");
                    return;
                }
                CurrInd = ResultInd + 1;
            }
            else {
                CurrInd++;
            }
        }
        Console.WriteLine("No");
    }
}

解説

最初に累積和を求めておきます。
次に、左から貪欲に始点にできるかを、バイナリサーチで調べます。

例えば
5,7,5の5を作りたいなら
(今の始点までの累積和 + 5)を バイナリサーチで探せば良いです。