ABC089-D Practical Skill Test

問題へのリンク

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 3 2");
            WillReturn.Add("1 4 3");
            WillReturn.Add("2 5 7");
            WillReturn.Add("8 9 6");
            WillReturn.Add("1");
            WillReturn.Add("4 8");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2 3");
            WillReturn.Add("3 7");
            WillReturn.Add("1 4");
            WillReturn.Add("5 2");
            WillReturn.Add("6 8");
            WillReturn.Add("2");
            WillReturn.Add("2 2");
            WillReturn.Add("2 2");
            //0
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5 5 4");
            WillReturn.Add("13 25 7 15 17");
            WillReturn.Add("16 22 20 2 9");
            WillReturn.Add("14 11 12 1 19");
            WillReturn.Add("10 6 23 8 18");
            WillReturn.Add("3 21 5 24 4");
            WillReturn.Add("3");
            WillReturn.Add("13 13");
            WillReturn.Add("2 10");
            WillReturn.Add("13 13");
            //0
            //5
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB_X;
    static int UB_Y;

    struct LRInfoDef
    {
        internal int L;
        internal int R;
    }
    static List<LRInfoDef> mLRInfoList = new List<LRInfoDef>();

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

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

        SplitAct(InputList[0]);
        int H = wkArr[0];
        int W = wkArr[1];
        int D = wkArr[2];

        int[,] BanArr = CreateBanArr(InputList.Skip(1).Take(H).ToList());
        UB_X = BanArr.GetUpperBound(0);
        UB_Y = BanArr.GetUpperBound(1);

        foreach (string EachStr in InputList.Skip(1 + H + 1)) {
            SplitAct(EachStr);
            LRInfoDef WillAdd;
            WillAdd.L = wkArr[0];
            WillAdd.R = wkArr[1];
            mLRInfoList.Add(WillAdd);
        }

        // マンハッタン距離を調べる用に、座標[数値]をDictに保存
        var PointDict = new Dictionary<int, PointDef>();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                int CurrNum = BanArr[LoopX, LoopY];
                PointDict[CurrNum] = new PointDef() { X = LoopX, Y = LoopY };
            }
        }

        // 数値ごとの(Dをスパンとした)累積和
        long[] RunSumArr = new long[H * W + 1];
        for (int I = 1; I <= RunSumArr.GetUpperBound(0); I++) {
            int PrevInd = I - D;
            if (PrevInd >= 1) {
                PointDef PrevPos = PointDict[PrevInd];
                PointDef CurrPos = PointDict[I];

                int AddX = Math.Abs(PrevPos.X - CurrPos.X);
                int AddY = Math.Abs(PrevPos.Y - CurrPos.Y);
                RunSumArr[I] += AddX + AddY;
                RunSumArr[I] += RunSumArr[PrevInd];
            }
        }

        foreach (LRInfoDef EachLRInfo in mLRInfoList) {
            int L = EachLRInfo.L;
            int R = EachLRInfo.R;
            Console.WriteLine(RunSumArr[R] - RunSumArr[L]);
        }
    }

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

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

        SplitAct(pStringList[0]);

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

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

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

    // 2次元配列のデバッグ出力
    static void PrintBan(int[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}

解説

前処理で、距離Dでの累積和を求めておいて
クエリに回答してます。