ABC268-E Chinese Restaurant (Three-Star Version)

問題へのリンク

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("1 2 0 3");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 1 2");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("3 9 6 1 7 2 8 0 5 4");
            //20
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] pArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int UB = pArr.GetUpperBound(0);
        int Len = pArr.Length;
        int MaxDistance = Len / 2;

        long[] RunSumArr = new long[Len * 2];

        long CurrScore = 0;
        for (int I = 0; I <= UB; I++) {
            int CurrVal = pArr[I];
            var GoalIndList = new List<int>();
            GoalIndList.Add(CurrVal - Len * 2);
            GoalIndList.Add(CurrVal - Len);
            GoalIndList.Add(CurrVal);
            GoalIndList.Add(CurrVal + Len);
            GoalIndList.Add(CurrVal + Len * 2);
            CurrScore += GoalIndList.Min(pX => Math.Abs(I - pX));

            var RangeInfoList = new List<RangeInfoDef>();
            int CurrInd = I;
            int IndLimit = I + Len;
            while (CurrInd < IndLimit) {
                int CurrDistance = GoalIndList.Min(pX => Math.Abs(CurrInd - pX));
                int NextDistance = GoalIndList.Min(pX => Math.Abs(CurrInd + 1 - pX));

                // 減少か変わらなかったら、0まで減少
                if (CurrDistance >= NextDistance) {
                    RangeInfoDef WillAdd1;
                    WillAdd1.RangeStaInd = CurrInd + 1;
                    WillAdd1.RangeEndInd = CurrInd + 1;
                    WillAdd1.Kaisa = NextDistance - CurrDistance;
                    RangeInfoList.Add(WillAdd1);

                    if (NextDistance > 0) {
                        RangeInfoDef WillAdd2;
                        WillAdd2.RangeStaInd = CurrInd + 2;
                        WillAdd2.RangeEndInd = WillAdd2.RangeStaInd + NextDistance - 1;
                        WillAdd2.Kaisa = -1;
                        RangeInfoList.Add(WillAdd2);
                        CurrInd = WillAdd2.RangeEndInd;
                    }
                    else {
                        CurrInd = WillAdd1.RangeEndInd;
                    }
                }
                // 増加したら、最大値まで増加
                if (CurrDistance < NextDistance) {
                    RangeInfoDef WillAdd1;
                    WillAdd1.RangeStaInd = CurrInd + 1;
                    WillAdd1.RangeEndInd = CurrInd + 1;
                    WillAdd1.Kaisa = 1;
                    RangeInfoList.Add(WillAdd1);

                    if (NextDistance < MaxDistance) {
                        RangeInfoDef WillAdd2;
                        WillAdd2.RangeStaInd = CurrInd + 2;
                        WillAdd2.RangeEndInd = WillAdd2.RangeStaInd + MaxDistance - NextDistance - 1;
                        WillAdd2.Kaisa = 1;
                        RangeInfoList.Add(WillAdd2);
                        CurrInd = WillAdd2.RangeEndInd;
                    }
                    else {
                        CurrInd = WillAdd1.RangeEndInd;
                    }
                }
            }

            foreach (RangeInfoDef EachRangeInfo in RangeInfoList) {
                int ImosSta = EachRangeInfo.RangeStaInd - I;
                int ImosEnd = EachRangeInfo.RangeEndInd - I + 1;

                RunSumArr[ImosSta] += EachRangeInfo.Kaisa;
                if (ImosEnd <= UB) {
                    RunSumArr[ImosEnd] -= EachRangeInfo.Kaisa;
                }
            }
        }

        long Answer = CurrScore;
        for (int I = 1; I <= UB; I++) {
            RunSumArr[I] += RunSumArr[I - 1];
            CurrScore += RunSumArr[I];
            Answer = Math.Min(Answer, CurrScore);
        }
        Console.WriteLine(Answer);
    }

    struct RangeInfoDef
    {
        internal int Kaisa;
        internal int RangeStaInd;
        internal int RangeEndInd;
    }
}

解説

料理ごとに1つ右に回転した時の不満度の差分を考えれば、
階差数列で考えることができます。

後は、階差数列の値と区間を考えて、いもす法で解くことができます。