典型90問 081 Friendly Group（★5）

問題へのリンク

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");
            WillReturn.Add("1 1");
            WillReturn.Add("2 5");
            WillReturn.Add("7 4");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 123");
            WillReturn.Add("4 5");
            WillReturn.Add("678 901");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("7 10");
            WillReturn.Add("20 20");
            WillReturn.Add("20 20");
            WillReturn.Add("20 30");
            WillReturn.Add("20 40");
            WillReturn.Add("30 20");
            WillReturn.Add("30 30");
            WillReturn.Add("40 20");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ABInfoDef
    {
        internal int A;
        internal int B;
    }
    static List<ABInfoDef> mABInfoList = new List<ABInfoDef>();

    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 K = wkArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ABInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.B = wkArr[1];
            mABInfoList.Add(WillAdd);
        }

        int UB_X = mABInfoList.Max(pX => pX.A);
        int UB_Y = mABInfoList.Max(pX => pX.B);

        int[,] RunSumArr = new int[UB_X + 1, UB_Y + 1];
        foreach (ABInfoDef EachABInfo in mABInfoList) {
            RunSumArr[EachABInfo.A, EachABInfo.B]++;
        }

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

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

        int Answer = 0;
        for (int StaX = 1; StaX <= UB_X; StaX++) {
            int EndX = StaX + K;
            EndX = Math.Min(EndX, UB_X);
            for (int StaY = 1; StaY <= UB_Y; StaY++) {
                int EndY = StaY + K;
                EndY = Math.Min(EndY, UB_Y);
                int CurrSum = DeriveSumRect(RunSumArr, EndX, EndY);
                CurrSum -= DeriveSumRect(RunSumArr, StaX - 1, EndY);
                CurrSum -= DeriveSumRect(RunSumArr, EndX, StaY - 1);
                CurrSum += DeriveSumRect(RunSumArr, StaX - 1, StaY - 1);
                Answer = Math.Max(Answer, CurrSum);
            }
        }
        Console.WriteLine(Answer);
    }

    // 指定座標の値を返す
    static int DeriveSumRect(int[,] pRunSumArr, int pX, int pY)
    {
        if (pX < 0) return 0;
        if (pY < 0) return 0;
        return pRunSumArr[pX, pY];
    }
}

解説

2次元累積和を使ってます