ABC210-D National Railway

問題へのリンク

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

    static long mC;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mC = wkArr[2];

        long[,] BanArr1 = CreateBanArr(InputList.Skip(1));
        long[,] BanArr2 = Kaiten90do(BanArr1);
        long[,] BanArr3 = Kaiten90do(BanArr2);
        long[,] BanArr4 = Kaiten90do(BanArr3);

        var DPResultList = new List<long>();
        DPResultList.Add(ExecDP(BanArr1));
        DPResultList.Add(ExecDP(BanArr2));
        DPResultList.Add(ExecDP(BanArr3));
        DPResultList.Add(ExecDP(BanArr4));

        Console.WriteLine(DPResultList.Min());
    }

    // 盤面を引数として、DPを行う
    static long ExecDP(long[,] pBanArr)
    {
        int UB_X = pBanArr.GetUpperBound(0);
        int UB_Y = pBanArr.GetUpperBound(1);

        // 最小コスト[X,Y,選択数]なDP表
        long?[, ,] DPArr = new long?[UB_X + 1, UB_Y + 1, 3];

        // 初期化しておく
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                DPArr[LoopX, LoopY, 0] = 0;
            }
        }

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopK = 1; 0 <= LoopK; LoopK--) {
                    Action<int, int, int, long> UpsertAct = (pNewX, pNewY, pNewK, pNewVal) =>
                    {
                        if (pNewX < 0 || UB_X < pNewX) return;
                        if (pNewY < 0 || UB_Y < pNewY) return;

                        if (DPArr[pNewX, pNewY, pNewK].HasValue) {
                            if (DPArr[pNewX, pNewY, pNewK] <= pNewVal) {
                                return;
                            }
                        }
                        DPArr[pNewX, pNewY, pNewK] = pNewVal;
                    };

                    if (DPArr[LoopX, LoopY, LoopK].HasValue == false) {
                        continue;
                    }
                    int NewK = LoopK + 1;
                    long NewVal;
                    if (NewK == 1) {
                        NewVal = -mC * (LoopX + LoopY) + pBanArr[LoopX, LoopY];
                    }
                    else {
                        NewVal = DPArr[LoopX, LoopY, 1].Value +
                            mC * (LoopX + LoopY) + pBanArr[LoopX, LoopY];
                    }
                    UpsertAct(LoopX, LoopY, NewK, NewVal);

                    long KakuteiVal = DPArr[LoopX, LoopY, NewK].Value;

                    // 確定したカレントの値を配る
                    UpsertAct(LoopX, LoopY + 1, NewK, KakuteiVal);
                    UpsertAct(LoopX + 1, LoopY, NewK, KakuteiVal);
                }
            }
        }

        long DPResult = long.MaxValue;
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (DPArr[LoopX, LoopY, 2].HasValue) {
                    DPResult = Math.Min(DPResult, DPArr[LoopX, LoopY, 2].Value);
                }
            }
        }
        return DPResult;
    }

    // 右に90度回転させた盤面を返す
    static Type[,] Kaiten90do<Type>(Type[,] pBanArr)
    {
        Type[,] WillReturn = new Type[pBanArr.GetUpperBound(1) + 1,
                                      pBanArr.GetUpperBound(0) + 1];

        for (int X = 0; X <= WillReturn.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= WillReturn.GetUpperBound(1); Y++) {
                WillReturn[X, Y] = pBanArr[Y, WillReturn.GetUpperBound(0) - X];
            }
        }
        return WillReturn;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static long[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new long[0, 0];
        }

        long[] IntArr = { };
        Action<string> SplitAct = pStr =>
            IntArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        long[,] WillReturn = new long[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

ベクトルの足し算で、原点を0として
任意の二点間のベクトルをABとすると
AB = OB - OA
が成り立つので
これを応用して、マンハッタン距離を分けて考えることができます。

これをふまえて、
最小コスト[X,Y,選択数] (ただし、選択数は0,1,2のいずれか)
を更新する、耳DPで解いてます。

マンハッタン距離の原点を盤面の左上、右上、右下、左下
とし、DPの配る方向が右と下の2方向しかないので
盤面を回転させてDPを行ってます。