ABC354-D AtCoder Wallpaper

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long A = wkArr[0];
        long B = wkArr[1];
        long C = wkArr[2];
        long D = wkArr[3];

        // 周期は4
        long Cycle = 4;

        // X座標を第1象限に移動
        long BekiVal = Cycle;
        while (A < 0) {
            A += BekiVal;
            C += BekiVal;
            BekiVal *= Cycle;
        }

        // Y座標を第1象限に移動
        BekiVal = Cycle;
        while (B < 0) {
            B += BekiVal;
            D += BekiVal;
            BekiVal *= Cycle;
        }

        // 格子点な座標から、グリッド座標に変換
        C--;
        D--;

        long[,] RunSumArr = new long[4, 2];
        RunSumArr[0, 0] = 2;
        RunSumArr[1, 0] = 3;
        RunSumArr[2, 0] = 3;
        RunSumArr[3, 0] = 4;

        RunSumArr[0, 1] = 3;
        RunSumArr[1, 1] = 6;
        RunSumArr[2, 1] = 7;
        RunSumArr[3, 1] = 8;

        var InsDeriveEuclidNumSum = new DeriveEuclidNumSum(RunSumArr);
        long Answer = InsDeriveEuclidNumSum.DeriveRectSum(A, B, C, D);
        Console.WriteLine(Answer);
    }
}

#region DeriveEuclidNumSum
// ユークリッド座標の矩形の数値和を求めるクラス
internal class DeriveEuclidNumSum
{
    private long[,] mRunSumArr;
    private long UB_X;
    private long UB_Y;
    private long mInitBanWidth;
    private long mInitBanHeight;

    // コンストラクタ(二次元累積和の配列が引数)
    internal DeriveEuclidNumSum(long[,] pRunSumArr)
    {
        mRunSumArr = pRunSumArr;
        UB_X = pRunSumArr.GetUpperBound(0);
        UB_Y = pRunSumArr.GetUpperBound(1);
        mInitBanWidth = UB_X + 1;
        mInitBanHeight = UB_Y + 1;
    }

    // (pStaX,pStaY)から(pEndX,pEndY)までの合計を求める
    internal long DeriveRectSum(long pStaX, long pStaY, long pEndX, long pEndY)
    {
        long CurrSum = DeriveSum(pEndX, pEndY);
        CurrSum -= DeriveSum(pStaX - 1, pEndY);
        CurrSum -= DeriveSum(pEndX, pStaY - 1);
        CurrSum += DeriveSum(pStaX - 1, pStaY - 1);
        return CurrSum;
    }

    // (0,0)から(pEndX,pEndY)までの合計を求める
    private 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 完全に含む盤面の分
    private long DeriveSumHelper1(long pEndX, long pEndY)
    {
        long AllWidth = pEndX + 1;
        long AllHeight = pEndY + 1;

        long Cnt1 = AllWidth / mInitBanWidth;
        long Cnt2 = AllHeight / mInitBanHeight;

        return mRunSumArr[UB_X, UB_Y] * Cnt1 * Cnt2;
    }

    // 分割2 下の盤面
    private long DeriveSumHelper2(long pEndX, long pEndY)
    {
        long AllWidth = pEndX + 1;
        long AllHeight = pEndY + 1;
        if (AllWidth % mInitBanWidth == 0) return 0;

        long Cnt = AllHeight / mInitBanHeight;
        long XMod = pEndX % mInitBanWidth;
        return mRunSumArr[XMod, UB_Y] * Cnt;
    }

    // 分割3 左の盤面
    private long DeriveSumHelper3(long pEndX, long pEndY)
    {
        long AllWidth = pEndX + 1;
        long AllHeight = pEndY + 1;
        if (AllHeight % mInitBanHeight == 0) return 0;

        long Cnt = AllWidth / mInitBanWidth;
        long YMod = pEndY % mInitBanHeight;
        return mRunSumArr[UB_X, YMod] * Cnt;
    }

    // 分割4 右上の盤面
    private long DeriveSumHelper4(long pEndX, long pEndY)
    {
        long AllWidth = pEndX + 1;
        long AllHeight = pEndY + 1;
        if (AllWidth % mInitBanWidth == 0) return 0;
        if (AllHeight % mInitBanHeight == 0) return 0;

        long XMod = pEndX % mInitBanWidth;
        long YMod = pEndY % mInitBanHeight;

        return mRunSumArr[XMod, YMod];
    }
}
#endregion

解説

横4マス、縦2マスの繰り返しで
LCM(4,2) = 4
なので、

ダブリングの感覚で、
X座標を第1象限に平行移動させ、
Y座標も第1象限に平行移動させます。

後は、二次元累積和を使い、解くことができます。

類題

ABC331-D Tile Pattern