ABC240-F Sum Sum Max

問題へのリンク

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("3");
            WillReturn.Add("3 7");
            WillReturn.Add("-1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("-3 2");
            WillReturn.Add("10 472");
            WillReturn.Add("-4 12");
            WillReturn.Add("1 29");
            WillReturn.Add("2 77");
            WillReturn.Add("-1 86");
            WillReturn.Add("0 51");
            WillReturn.Add("3 81");
            WillReturn.Add("3 17");
            WillReturn.Add("-2 31");
            WillReturn.Add("-4 65");
            WillReturn.Add("4 23");
            WillReturn.Add("1 1000000000");
            WillReturn.Add("4 1000000000");
            //4
            //53910
            //2000000002000000000
        }
        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 mN;
    static long mM;

    struct RLEInfoDef
    {
        internal long Val;
        internal long Len;
    }
    static List<RLEInfoDef> mRLEInfoList = new List<RLEInfoDef>();

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        int CurrInd = 1;
        while (true) {
            if (CurrInd > InputList.Count - 1) {
                break;
            }
            SplitAct(InputList[CurrInd]);
            mN = wkArr[0];
            mM = wkArr[1];

            mRLEInfoList.Clear();
            for (int I = 1; I <= mN; I++) {
                SplitAct(InputList[CurrInd + I]);
                RLEInfoDef WillAdd;
                WillAdd.Val = wkArr[0];
                WillAdd.Len = wkArr[1];
                mRLEInfoList.Add(WillAdd);
            }
            long Result = Solve();
            Console.WriteLine(Result);
            CurrInd += (int)mN + 1;
        }
    }

    static long Solve()
    {
        mTousaInfoList.Clear();

        long CurrSum = 0;
        foreach (RLEInfoDef EachRLEInfo in mRLEInfoList) {
            TousaInfoDef WillAdd;
            WillAdd.Syokou = CurrSum + EachRLEInfo.Val;
            WillAdd.Kousa = EachRLEInfo.Val;
            WillAdd.Kousuu = EachRLEInfo.Len;
            WillAdd.Makkou = WillAdd.Syokou + WillAdd.Kousa * (WillAdd.Kousuu - 1);
            mTousaInfoList.Add(WillAdd);
            CurrSum += EachRLEInfo.Val * EachRLEInfo.Len;
        }

        long Annswer = long.MinValue;
        long CurrRunSum = 0;
        foreach (TousaInfoDef EachTousaInfo in mTousaInfoList) {
            long Result = CurrRunSum +
                ExecSanbuntansaku(EachTousaInfo.Syokou, EachTousaInfo.Kousa, EachTousaInfo.Kousuu);

            Annswer = Math.Max(Annswer, Result);

            CurrRunSum +=
                DeriveTousaSuuretuSum(EachTousaInfo.Syokou, EachTousaInfo.Kousa, EachTousaInfo.Kousuu);
        }

        return Annswer;
    }

    // 等差数列の情報
    struct TousaInfoDef
    {
        internal long Syokou; // 初項
        internal long Kousa;  // 公差
        internal long Kousuu; // 項数
        internal long Makkou; // 末項
    }
    static List<TousaInfoDef> mTousaInfoList = new List<TousaInfoDef>();

    // 三分探索で極大値を求める
    static long ExecSanbuntansaku(long pSyokou, long pKousa, long pKouCnt)
    {
        long L = 1;
        long R = pKouCnt;

        // 番目を引数として、関数値を返す
        Func<long, long> CalcFunc = pBanme =>
        {
            return DeriveTousaSuuretuSum(pSyokou, pKousa, pBanme);
        };

        while (L + 1 < R) {
            long BeforeL = L, BeforeR = R;
            long C1 = (L * 2 + R) / 3;
            long C2 = (L + R * 2) / 3;

            long C1Val = CalcFunc(C1);
            long C2Val = CalcFunc(C2);

            if (C1Val > C2Val) {
                R = C2;
                if (R == BeforeR) break;
            }
            else {
                L = C1;
                if (L == BeforeL) break;
            }
        }

        var MaxKouhoList = new List<long>();
        for (long I = L; I <= R; I++) {
            MaxKouhoList.Add(CalcFunc(I));
        }
        return MaxKouhoList.Max();
    }

    // 初項と公差と項数を引数として、等差数列の和を返す
    static long DeriveTousaSuuretuSum(long pSyokou, long pKousa, long pKouCnt)
    {
        long Makkou = pSyokou + pKousa * (pKouCnt - 1);
        long wkSum = pSyokou + Makkou;
        long Result = wkSum * pKouCnt;
        Result /= 2;
        return Result;
    }
}

解説

配列Aは速度の増減
配列Bは速度
配列Cは移動距離
と考えることができます。

配列Bは等差数列なので、
配列Cは等差数列の和の公式で求まります。

等差数列の和の公式は、二次式なので極値は、1つです。
なので、等差数列ごとの三分探索で解けます。