ABC331-D Tile Pattern

問題へのリンク

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 2");
            WillReturn.Add("WWB");
            WillReturn.Add("BBW");
            WillReturn.Add("WBW");
            WillReturn.Add("1 2 3 4");
            WillReturn.Add("0 3 4 5");
            //4
            //7
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 5");
            WillReturn.Add("BBBWWWBBBW");
            WillReturn.Add("WWWWWBBBWB");
            WillReturn.Add("BBBWBBWBBB");
            WillReturn.Add("BBBWWBWWWW");
            WillReturn.Add("WWWWBWBWBW");
            WillReturn.Add("WBBWBWBBBB");
            WillReturn.Add("WWBBBWWBWB");
            WillReturn.Add("WBWBWWBBBB");
            WillReturn.Add("WBWBWBBWWW");
            WillReturn.Add("WWWBWWBWWB");
            WillReturn.Add("5 21 21 93");
            WillReturn.Add("35 35 70 43");
            WillReturn.Add("55 72 61 84");
            WillReturn.Add("36 33 46 95");
            WillReturn.Add("0 0 999999999 999999999");
            //621
            //167
            //44
            //344
            //500000000000000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long UB;
    static char[,] mBanArr;
    static long[,] mRunSumArr;

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

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

        SplitAct(InputList[0]);
        mN = wkArr[0];
        UB = mN - 1;

        mBanArr = CreateBanArr(InputList.Skip(1).Take((int)mN));

        // 2次元累積和を求める
        mRunSumArr = new long[UB + 1, UB + 1];
        for (long LoopX = 0; LoopX <= UB; LoopX++) {
            for (long LoopY = 0; LoopY <= UB; LoopY++) {
                if (mBanArr[LoopX, LoopY] == 'B') mRunSumArr[LoopX, LoopY] = 1;
            }
        }

        // 累積和を設定する (横方向)
        for (long LoopX = 1; LoopX <= UB; LoopX++) {
            for (long LoopY = 0; LoopY <= UB; LoopY++) {
                mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX - 1, LoopY];
            }
        }

        // 累積和を設定する (縦方向)
        for (long LoopX = 0; LoopX <= UB; LoopX++) {
            for (long LoopY = 1; LoopY <= UB; LoopY++) {
                mRunSumArr[LoopX, LoopY] += mRunSumArr[LoopX, LoopY - 1];
            }
        }

        foreach (string EachStr in InputList.Skip(1 + (int)mN)) {
            SplitAct(EachStr);
            long StaY = wkArr[0];
            long StaX = wkArr[1];
            long EndY = wkArr[2];
            long EndX = wkArr[3];

            long CurrSum = DeriveSum(EndX, EndY);
            CurrSum -= DeriveSum(StaX - 1, EndY);
            CurrSum -= DeriveSum(EndX, StaY - 1);
            CurrSum += DeriveSum(StaX - 1, StaY - 1);
            Console.WriteLine(CurrSum);
        }
    }

    // (0,0)から(pEndX,pEndY)までの合計を求める
    static long DeriveSum(long pEndX, long pEndY)
    {
        if (pEndX < 0) return 0;
        if (pEndY < 0) return 0;

        var CntList = new List<long>();

        CntList.Add(DeriveSumHelper1(pEndX, pEndY));
        CntList.Add(DeriveSumHelper2(pEndX, pEndY));
        CntList.Add(DeriveSumHelper3(pEndX, pEndY));
        CntList.Add(DeriveSumHelper4(pEndX, pEndY));

        return CntList.Sum();
    }

    // 分割1 完全に含む盤面の分
    static long DeriveSumHelper1(long pEndX, long pEndY)
    {
        long Width = pEndX + 1;
        long Height = pEndY + 1;

        long Cnt1 = Width / mN;
        long Cnt2 = Height / mN;

        return mRunSumArr[UB, UB] * Cnt1 * Cnt2;
    }

    // 分割2 上の盤面
    static long DeriveSumHelper2(long pEndX, long pEndY)
    {
        long Width = pEndX + 1;
        long Height = pEndY + 1;
        if (Width % mN == 0) return 0;

        long Cnt = Height / mN;
        long XMod = pEndX % mN;
        return mRunSumArr[XMod, UB] * Cnt;
    }

    // 分割3 左の盤面
    static long DeriveSumHelper3(long pEndX, long pEndY)
    {
        long Width = pEndX + 1;
        long Height = pEndY + 1;
        if (Height % mN == 0) return 0;

        long Cnt = Width / mN;
        long YMod = pEndY % mN;
        return mRunSumArr[UB, YMod] * Cnt;
    }

    // 分割4 右下の盤面
    static long DeriveSumHelper4(long pEndX, long pEndY)
    {
        long Width = pEndX + 1;
        long Height = pEndY + 1;
        if (Width % mN == 0) return 0;
        if (Height % mN == 0) return 0;

        long XMod = pEndX % mN;
        long YMod = pEndY % mN;

        return mRunSumArr[XMod, YMod];
    }

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

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

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

解説

(0,0)から(pX,pY)までの黒マスの数を求めるメソッドを作ってます。

基準の盤面が3*3として、
9*9の盤面を書いて、
4分割のロジックを考えてます。

□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□