ABC147-E Balanced Path

問題へのリンク

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

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

        int H = wkArr[0];
        int W = wkArr[1];

        int[,] BanArrA = CreateBanArr(InputList.Skip(1).Take(H));
        int[,] BanArrB = CreateBanArr(InputList.Skip(1 + H));

        int UB_X = W - 1;
        int UB_Y = H - 1;

        int[,] DiffArr = new int[UB_X + 1, UB_Y + 1];
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                int ValA = BanArrA[LoopX, LoopY];
                int ValB = BanArrB[LoopX, LoopY];
                DiffArr[LoopX, LoopY] = Math.Abs(ValA - ValB);
            }
        }

        // 到達可否[X座標,Y座標,差]なDP表
        int UB_Z = 80 * (80 + 80);
        bool[, ,] DPArr = new bool[UB_X + 1, UB_Y + 1, UB_Z + 1];
        DPArr[0, 0, DiffArr[0, 0]] = true;

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopZ = 0; LoopZ <= UB_Z; LoopZ++) {
                    if (DPArr[LoopX, LoopY, LoopZ] == false) continue;

                    // 配るDPで右に配る
                    if (LoopX < UB_X) {
                        int Kubaru1 = Math.Abs(LoopZ + DiffArr[LoopX + 1, LoopY]);
                        int Kubaru2 = Math.Abs(LoopZ - DiffArr[LoopX + 1, LoopY]);
                        DPArr[LoopX + 1, LoopY, Kubaru1] = true;
                        DPArr[LoopX + 1, LoopY, Kubaru2] = true;
                    }
                    // 配るDPで下に配る
                    if (LoopY < UB_Y) {
                        int Kubaru1 = Math.Abs(LoopZ + DiffArr[LoopX, LoopY + 1]);
                        int Kubaru2 = Math.Abs(LoopZ - DiffArr[LoopX, LoopY + 1]);
                        DPArr[LoopX, LoopY + 1, Kubaru1] = true;
                        DPArr[LoopX, LoopY + 1, Kubaru2] = true;
                    }
                }
            }
        }

        for (int LoopZ = 0; LoopZ <= UB_Z; LoopZ++) {
            if (DPArr[UB_X, UB_Y, LoopZ]) {
                Console.WriteLine(LoopZ);
                return;
            }
        }
    }

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

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

        SplitAct(StrList[0]);

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

        int[,] WillReturn = new int[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;
    }
}

解説

最初の考察として、
マスにある2つの数を
赤の総和か、青の総和
の片方ずつに加算するので

赤の総和と青の総和の差は、
マスにある2つの数の差の分だけ
増えるか減るかになると分かります。

この考察をしてから、
到達可否[X座標,Y座標,差]を更新するDPで解いてます。