第4回PAST I ピザ

問題へのリンク

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");
            WillReturn.Add("10 20 40 30");
            //20
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            WillReturn.Add("13 76 46 15 50 98 93 77 31 43 84 90 6 24 14 37 73 29 43 9");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] mAArr;
    static List<long> mATwiceList = new List<long>();
    static long mAArrSum;

    static List<long> mATwiceRunSumList;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mAArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mAArrSum = mAArr.Sum();

        mATwiceList.AddRange(mAArr);
        mATwiceList.AddRange(mAArr);

        mATwiceRunSumList = new List<long>(mATwiceList);

        // 累積和を求めておく
        for (int I = 0; I <= mATwiceList.Count - 1; I++) {
            mATwiceRunSumList[I] = mATwiceList[I];
            if (0 < I) {
                mATwiceRunSumList[I] += mATwiceRunSumList[I - 1];
            }
        }

        // 始点を全探索して、三分探索を行う
        long Answer = long.MaxValue;
        for (long I = 0; I <= mAArr.GetUpperBound(0); I++) {
            long ResultSanbuntansaku = ExecSanbuntansaku(I);
            //Console.WriteLine("始点が{0}の場合の、解候補={1}", I, ResultSanbuntansaku);
            Answer = Math.Min(Answer, ResultSanbuntansaku);
        }
        Console.WriteLine(Answer);
    }

    // 始点を引数として、三分探索で極値を求める
    static long ExecSanbuntansaku(long pStaInd)
    {
        //Console.WriteLine("StaInd={0}で三分探索を行います", pStaInd);
        long L = 0;            // 取得個数の最小値
        long R = mAArr.Length; // 取得個数の最大値

        var PairHashSet = new HashSet<long>();
        while (L + 1 < R) {
            long C1 = (L * 2 + R) / 3;
            long C2 = (L + R * 2) / 3;

            long RangeSum1 = DeriveRangeSum(pStaInd, C1);
            long RangeSum2 = DeriveRangeSum(pStaInd, C2);

            long Rest1 = mAArrSum - RangeSum1;
            long Rest2 = mAArrSum - RangeSum2;

            long C1Val = Math.Abs(RangeSum1 - Rest1);
            long C2Val = Math.Abs(RangeSum2 - Rest2);

            if (C1Val < C2Val) {
                R = C2;
            }
            else {
                L = C1;
            }
            long Hash = L * 1000000 + R;
            if (PairHashSet.Add(Hash) == false) {
                break;
            }
        }

        var MinKouhoList = new List<long>();
        for (long I = L; I <= R; I++) {
            long RangeSum = DeriveRangeSum(pStaInd, I);
            long Rest = mAArrSum - RangeSum;
            long CVal = Math.Abs(RangeSum - Rest);
            MinKouhoList.Add(CVal);
        }
        return MinKouhoList.Min();
    }

    // 始点と取得数を引数として、総和を返す
    static long DeriveRangeSum(long pStaInd, long pCnt)
    {
        if (pCnt == 0) return 0;

        long pEndInd = pStaInd + pCnt - 1;
        return mATwiceRunSumList[(int)pEndInd]
            - mATwiceRunSumList[(int)pStaInd]
            + mATwiceList[(int)pStaInd];
    }
}

解説

10 20 40 30
で始点を0に固定して、取得数を増やして考察します。

取得数=0だと、取得した合計=  0、取得しなかった合計=100、差=100
取得数=1だと、取得した合計= 10、取得しなかった合計= 90、差= 80
取得数=2だと、取得した合計= 30、取得しなかった合計= 70、差= 40
取得数=3だと、取得した合計= 70、取得しなかった合計= 30、差= 40
取得数=4だと、取得した合計=100、取得しなかった合計=  0、差=100

下に凸な分布と分かるので、始点を全探索しつつ
始点ごとに、三分探索を使ってます。

また、環状は扱いにくいので、配列を2つに重ねてます。