ABC004-D マーブル

問題へのリンク

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("2 3 4");
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("17 2 34");
            //362
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("267 294 165");
            //88577
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mR;
    static int mG;
    static int mB;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mR = wkArr[0];
        mG = wkArr[1];
        mB = wkArr[2];

        int UB_I = 3000;

        // 最小コスト[現在位置 , Rの設置有無 , Gの設置有無 , Bの設置有無]
        int?[, , ,] DPArr = new int?[UB_I + 1, 2, 2, 2];
        DPArr[0, 0, 0, 0] = 0;

        // 配るDP
        for (int I = 0; I <= UB_I; I++) {
            for (int J = 0; J <= 1; J++) {
                for (int K = 0; K <= 1; K++) {
                    for (int L = 0; L <= 1; L++) {
                        if (DPArr[I, J, K, L].HasValue == false) {
                            continue;
                        }
                        int CurrCost = DPArr[I, J, K, L].Value;

                        // 設置しない経路
                        if (I + 1 <= UB_I) {
                            int NewI = I + 1;
                            if (DPArr[NewI, J, K, L].HasValue == false
                            || DPArr[NewI, J, K, L].Value > CurrCost) {
                                DPArr[NewI, J, K, L] = CurrCost;
                            }
                        }

                        // Rを設置する経路
                        if (J == 0 && K == 0 && L == 0) {
                            int NewI = I + mR;
                            if (NewI <= UB_I) {
                                int NewCost = CurrCost + DeriveCost('R', I);
                                if (DPArr[NewI, 1, 0, 0].HasValue == false
                                || DPArr[NewI, 1, 0, 0].Value > NewCost) {
                                    DPArr[NewI, 1, 0, 0] = NewCost;
                                }
                            }
                        }

                        // Gを設置する経路
                        if (J == 1 && K == 0 && L == 0) {
                            int NewI = I + mG;
                            if (NewI <= UB_I) {
                                int NewCost = CurrCost + DeriveCost('G', I);
                                if (DPArr[NewI, 1, 1, 0].HasValue == false
                                || DPArr[NewI, 1, 1, 0].Value > NewCost) {
                                    DPArr[NewI, 1, 1, 0] = NewCost;
                                }
                            }
                        }

                        // Bを設置する経路
                        if (J == 1 && K == 1 && L == 0) {
                            int NewI = I + mB;
                            if (NewI <= UB_I) {
                                int NewCost = CurrCost + DeriveCost('B', I);
                                if (DPArr[NewI, 1, 1, 1].HasValue == false
                                || DPArr[NewI, 1, 1, 1].Value > NewCost) {
                                    DPArr[NewI, 1, 1, 1] = NewCost;
                                }
                            }
                        }
                    }
                }
            }
        }

        int Answer = int.MaxValue;
        for (int I = 0; I <= UB_I; I++) {
            if (DPArr[I, 1, 1, 1].HasValue) {
                Answer = Math.Min(Answer, DPArr[I, 1, 1, 1].Value);
            }
        }
        Console.WriteLine(Answer);
    }

    // 設置した時のコストを求める
    static int DeriveCost(char pSetColor, int pCurrPos)
    {
        int BasePos = 1400;
        if (pSetColor == 'G') BasePos = 1500;
        if (pSetColor == 'B') BasePos = 1600;

        int MarbleCnt = mR;
        if (pSetColor == 'G') MarbleCnt = mG;
        if (pSetColor == 'B') MarbleCnt = mB;

        int LeftPos = pCurrPos;
        int RightPos = pCurrPos + MarbleCnt - 1;

        if (LeftPos <= BasePos && BasePos <= RightPos) {
            int Cost = DeriveSum(Math.Abs(LeftPos - BasePos), 0);
            Cost += DeriveSum(Math.Abs(RightPos - BasePos), 0);
            return Cost;
        }
        else {
            int Cost = DeriveSum(Math.Abs(LeftPos - BasePos), Math.Abs(RightPos - BasePos));
            return Cost;
        }
    }

    // 初項と末項を引数として、公差1の等差数列の和を返す
    static int DeriveSum(int pSyokou, int pMakkou)
    {
        int Kousuu = Math.Abs(pSyokou - pMakkou) + 1;
        return (pSyokou + pMakkou) * Kousuu / 2;
    }
}

解説

最終形は、左から順に
1個以上のR、0個以上の空白、1個以上のG、0個以上の空白、1個以上のB
になります。

なので、左から位置を走査していって、
最小コスト[現在位置 , Rの設置有無 , Gの設置有無 , Bの設置有無]
を更新するDPで解けます。

RやGやBを設置した時にかかるコストは、
等差数列の和の公式で高速に求めることができます。