典型90問 028 Cluttered Paper（★4）

問題へのリンク

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");
            WillReturn.Add("1 1 3 2");
            WillReturn.Add("2 1 4 2");
            //2
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("1 1 3 4");
            WillReturn.Add("3 4 6 5");
            //9
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20");
            WillReturn.Add("61 98 76 100");
            WillReturn.Add("70 99 95 100");
            WillReturn.Add("10 64 96 91");
            WillReturn.Add("12 37 99 66");
            WillReturn.Add("63 93 65 95");
            WillReturn.Add("16 18 18 67");
            WillReturn.Add("30 47 88 56");
            WillReturn.Add("33 6 38 8");
            WillReturn.Add("37 19 40 68");
            WillReturn.Add("4 56 12 84");
            WillReturn.Add("3 16 92 78");
            WillReturn.Add("39 24 67 96");
            WillReturn.Add("46 1 69 57");
            WillReturn.Add("40 34 65 65");
            WillReturn.Add("20 38 51 92");
            WillReturn.Add("5 32 100 73");
            WillReturn.Add("7 33 92 55");
            WillReturn.Add("4 46 97 85");
            WillReturn.Add("43 18 57 87");
            WillReturn.Add("15 29 54 74");
            //1806
            //990
            //1013
            //1221
            //567
            //839
            //413
            //305
            //228
            //121
            //58
            //40
            //0
            //0
            //0
            //0
            //0
            //0
            //0
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct RectInfoDef
    {
        internal int X1;
        internal int Y1;
        internal int X2;
        internal int Y2;
    }
    static List<RectInfoDef> mRectInfoList = new List<RectInfoDef>();

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

        int N = int.Parse(InputList[0]);

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RectInfoDef WillAdd;
            WillAdd.X1 = wkArr[0];
            WillAdd.Y1 = wkArr[1];
            WillAdd.X2 = wkArr[2] - 1; // マス目で考えたいので1引く
            WillAdd.Y2 = wkArr[3] - 1; // マス目で考えたいので1引く
            mRectInfoList.Add(WillAdd);
        }

        int UB_X = mRectInfoList.Max(pX => pX.X2);
        int UB_Y = mRectInfoList.Max(pX => pX.Y2);

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

        foreach (RectInfoDef EachRectInfo in mRectInfoList) {
            int StaX = EachRectInfo.X1;
            int StaY = EachRectInfo.Y1;
            int EndX = EachRectInfo.X2 + 1;
            int EndY = EachRectInfo.Y2 + 1;

            ImosArr[StaX, StaY]++;
            if (EndX <= UB_X) {
                ImosArr[EndX, StaY]--;
            }
            if (EndY <= UB_Y) {
                ImosArr[StaX, EndY]--;
            }
            if (EndX <= UB_X && EndY <= UB_Y) {
                ImosArr[EndX, EndY]++;
            }
        }

        // 横方向の累積和を求める
        for (int X = 1; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                ImosArr[X, Y] += ImosArr[X - 1, Y];
            }
        }

        // 縦方向の累積和を求める
        for (int Y = 1; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                ImosArr[X, Y] += ImosArr[X, Y - 1];
            }
        }

        var CntDict = new Dictionary<int, int>();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                int CurrVal = ImosArr[X, Y];
                if (CntDict.ContainsKey(CurrVal) == false) {
                    CntDict[CurrVal] = 0;
                }
                CntDict[CurrVal]++;
            }
        }

        for (int I = 1; I <= N; I++) {
            if (CntDict.ContainsKey(I)) {
                Console.WriteLine(CntDict[I]);
            }
            else {
                Console.WriteLine(0);
            }
        }
    }
}

解説

2次元いもす法を使ってます。