ABC285-E Work or Rest

問題へのリンク

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("7");
            WillReturn.Add("10 10 1 1 1 1 1");
            //50
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20");
            //5100000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add("38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680");
            //236980
        }
        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 Fenwick_Tree mInsFenwick_Tree;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

        long[] AArr = GetSplitArr(InputList[1]);
        mInsFenwick_Tree = new Fenwick_Tree(AArr);

        // 最大スコア[最後に休日にした日]なインラインDP表
        long?[] DPArr = new long?[N + 1];

        // 1日目は必ず休日とする
        DPArr[1] = 0;

        for (long I = 2; I <= N; I++) {
            for (long J = I - 1; 1 <= J; J--) {
                if (DPArr[J].HasValue == false) {
                    continue;
                }

                long NewJ = I;
                long NewVal = DPArr[J].Value + GetScoreSum(J, I);

                if (DPArr[NewJ].HasValue) {
                    if (DPArr[NewJ] >= NewVal) {
                        continue;
                    }
                }
                DPArr[NewJ] = NewVal;
            }

            //Console.WriteLine("{0}日目のDP結果", I);
            //for (long J = 1; J <= I; J++) {
            //    if (DPArr[J].HasValue == false) {
            //        continue;
            //    }
            //    Console.WriteLine("DPArr[{0}]={1}", J, DPArr[J]);
            //}
        }

        // 環状なので、1日目に対応する(N+1)日目も休日とし、解候補にする
        var AnswerList = new List<long>();
        for (long I = 1; I <= N; I++) {
            if (DPArr[I].HasValue == false) {
                continue;
            }
            long NewVal = DPArr[I].Value + GetScoreSum(I, N + 1);
            AnswerList.Add(NewVal);
        }
        Console.WriteLine(AnswerList.Max());
    }

    // 2つの休日を引数とし、間のスコアを計算
    static long GetScoreSum(long pHoliday1, long pHoliday2)
    {
        // 間の平日数
        long DayCnt = pHoliday2 - pHoliday1 - 1;
        if (DayCnt <= 0) return 0;

        long ScoreSum = 0;

        // 2回集計する分
        long Div2 = DayCnt / 2;
        long Mod2 = DayCnt % 2;
        if (Div2 > 0) {
            ScoreSum += 2 * mInsFenwick_Tree.GetSum(0, Div2 - 1);
        }

        // 1回だけ集計する分
        if (Mod2 == 1) {
            ScoreSum += mInsFenwick_Tree[Div2];
        }
        return ScoreSum;
    }
}

// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mExternalArrUB;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ(外部配列のUBのみ指定)
    internal Fenwick_Tree(long pExternalArrUB)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];
    }

    // コンストラクタ(初期化用の配列指定)
    internal Fenwick_Tree(long[] pArr)
        : this(pArr.GetUpperBound(0))
    {
        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            this.Add(I, pArr[I]);
        }
    }

    // コンストラクタ(初期化用のList指定)
    internal Fenwick_Tree(List<long> pList)
        : this(pList.Count - 1)
    {
        for (int I = 0; I <= pList.Count - 1; I++) {
            this.Add(I, pList[I]);
        }
    }

    // Indのチェック
    private void IndCheck(long pInd)
    {
        if (pInd < 0) throw new Exception("pInd < 0");
        if (mExternalArrUB < 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");
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

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

        long Result = GetSum(pEnd);
        if (pSta > 0) {
            Result -= GetSum(pSta - 1);
        }
        return Result;
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        IndCheck(pEnd);

        pEnd++; // 1オリジンに変更

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX)
    {
        IndCheck(pI);

        pI++; // 1オリジンに変更

        while (pI <= mBitArr.GetUpperBound(0)) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion

解説

必ず休日は1日必要であり、
休日からの距離でスコアが決まるため、
初日を休日で固定しても問題ありません。

よって、N日間の内、1日目を休日として考えます。
すると、環状なため、(N+1)日目も休日にする必要がありますが、
これは、最後に考慮することにします。

図を書いて、考えます。
休□□□□□□□□□□□□

最大スコア[最後に休日にした日]を状態に持って、
左から順に日を見ていき、
平日にするなら、スコア増加は無し(遷移なし)
休日にするなら、スコア増加は有り(遷移あり)
なDPで解くことができます。

スコア増加は、連続した平日数と
スコア配列を設定したフェニック木を前処理で作成しておくことで
高速に求めることができます。

最後に、各状態から、(N+1)日目を休日にした状態に
遷移すれば、解候補を求めることができます。

なお、「最後に休日にした日」は必ず増えるので、インラインDPにできます。

計算量は、O(N*N*2*log(N)))なので、間に合います。