ABC475-C Walk the Line

問題へのリンク

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("6 3 10");
            WillReturn.Add("5 2 4 1 6");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("8 8 17");
            WillReturn.Add("2 3 4 4 3 5 1");
            //6
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 1 1000000000000000000");
            WillReturn.Add("10000");
            //2
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("9 6 28");
            WillReturn.Add("5 4 9 2 3 6 1 4");
            //6
        }
        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 RangeSumClass mInsRangeSum;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long N = wkArr[0];
        long Sta = wkArr[1] * 2; // 2倍にして考える
        long L = wkArr[2];

        mInsRangeSum = new RangeSumClass(N * 2);

        long[] AArr = GetSplitArr(InputList[1]);
        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long Ind = 2 * I + 3;
            mInsRangeSum[Ind] = AArr[I];
        }

        var TwiceList = new List<long>();
        for (long I = 1; I <= N; I++) {
            TwiceList.Add(I * 2);
        }

        long Answer = 1;
        foreach (long EachPos1 in TwiceList) {
            long Cost1 = Getkyori(Sta, EachPos1);
            if (Cost1 > L) continue;
            foreach (long EachPos2 in TwiceList) {
                long Cost2 = Getkyori(EachPos1, EachPos2);
                if (Cost1 + Cost2 > L) continue;

                long MinPos = Sta;
                long MaxPos = Sta;
                MinPos = Math.Min(MinPos, EachPos1);
                MinPos = Math.Min(MinPos, EachPos2);
                MaxPos = Math.Max(MaxPos, EachPos1);
                MaxPos = Math.Max(MaxPos, EachPos2);
                long CurrAnswer = (MaxPos - MinPos) / 2 + 1;

                Answer = Math.Max(Answer, CurrAnswer);
            }
        }
        Console.WriteLine(Answer);
    }

    static long Getkyori(long pSta, long pEnd)
    {
        if (pSta == pEnd) return 0;
        long Min = Math.Min(pSta, pEnd);
        long Max = Math.Max(pSta, pEnd);

        return mInsRangeSum.GetRangeSum(Min, Max);
    }
}

// 前処理で累積和をO(N)で求め、区間和をO(1)で求める
// 更新不可なフェニック木のイメージ
#region RangeSumClass
internal class RangeSumClass
{
    private long[] mValArr;
    private long UB;

    private bool mArrIsRunSum = false; // 配列を累積和に変換済か？

    // Indexの列挙を返す
    internal IEnumerable<long> GetIndEnum()
    {
        for (long I = 0; I <= UB; I++) {
            yield return I;
        }
    }

    // UBを返す
    internal long GetUB()
    {
        return UB;
    }

    // コンストラクタ(配列のUBのみ指定)
    internal RangeSumClass(long pUB)
    {
        UB = pUB;
        mValArr = new long[pUB + 1];
    }

    // インデクサ
    internal long this[long pInd]
    {
        get
        {
            if (mArrIsRunSum) throw new Exception("既に累積和に変換済なので取得できません");
            return mValArr[pInd];
        }

        set
        {
            if (mArrIsRunSum) throw new Exception("既に累積和に変換済なので更新できません");
            mValArr[pInd] = value;
        }
    }

    // コンストラクタ(初期化用の配列指定)
    internal RangeSumClass(long[] pValArr)
    {
        mValArr = (long[])pValArr.Clone();
        UB = mValArr.GetUpperBound(0);
    }

    // コンストラクタ(初期化用のList指定)
    internal RangeSumClass(List<long> pValList)
    {
        mValArr = pValList.ToArray();
        UB = mValArr.GetUpperBound(0);
    }

    // Indのチェック
    private void IndCheck(long pInd)
    {
        if (pInd < 0) throw new Exception("pInd < 0");
        if (UB < pInd) throw new Exception("UB < pInd");
    }

    // Indの大小チェック
    private void IndRangeCheck(long pSta, long pEnd)
    {
        IndCheck(pSta);
        IndCheck(pEnd);
        if (pSta > pEnd) throw new Exception("pSta > pEnd");
    }

    // [pSta,pEnd] のSumを返す
    internal long GetRangeSum(long pSta, long pEnd)
    {
        IndRangeCheck(pSta, pEnd);

        // 累積和に変換する
        if (mArrIsRunSum == false) {
            for (long I = 1; I <= UB; I++) {
                mValArr[I] += mValArr[I - 1];
            }
            mArrIsRunSum = true;
        }

        long RunSum = mValArr[pEnd];
        if (pSta > 0) {
            RunSum -= mValArr[pSta - 1];
        }
        return RunSum;
    }

    // [0,pEnd] のSumを返す
    internal long GetRangeSum(long pEnd)
    {
        return GetRangeSum(0, pEnd);
    }
}
#endregion

解説

図で考えます。

1---2---3---4---5---6
  5   2   4   1   6

区間和を求めるデータ構造を使いやすいように、
頂点のIndを2倍して考えます。

2---4---6---8---10---12
  5   2   4   1    6

すると、コストの箇所に奇数のIndを設定し、区間和を求めやすくなります。

あとは、2回の移動の組み合わせを全て試せば、解が分かります。
O(N*N)でも6400万なので、間に合います。