AtCoderのABC    次のABCの問題へ    前のABCの問題へ

ABC278-E Grid Filling


問題へのリンク


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

    class NumInfo
    {
        internal int MinX;
        internal int MaxX;
        internal int MinY;
        internal int MaxY;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int RangeX = wkArr[4];
        int RangeY = wkArr[3];

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

        var NumInfoDict = new Dictionary<int, NumInfo>();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                int CurrNum = BanArr[LoopX, LoopY];

                if (NumInfoDict.ContainsKey(CurrNum) == false) {
                    NumInfoDict[CurrNum] = new NumInfo();
                    NumInfoDict[CurrNum].MinX = LoopX;
                    NumInfoDict[CurrNum].MaxX = LoopX;
                    NumInfoDict[CurrNum].MinY = LoopY;
                    NumInfoDict[CurrNum].MaxY = LoopY;
                }
                else {
                    NumInfoDict[CurrNum].MinX = Math.Min(NumInfoDict[CurrNum].MinX, LoopX);
                    NumInfoDict[CurrNum].MaxX = Math.Max(NumInfoDict[CurrNum].MaxX, LoopX);

                    NumInfoDict[CurrNum].MinY = Math.Min(NumInfoDict[CurrNum].MinY, LoopY);
                    NumInfoDict[CurrNum].MaxY = Math.Max(NumInfoDict[CurrNum].MaxY, LoopY);
                }
            }
        }

        var sb = new System.Text.StringBuilder();
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            int YLimit = LoopY + RangeY - 1;
            if (YLimit > UB_Y) break;

            var AnswerList = new List<int>();
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                int XLimit = LoopX + RangeX - 1;
                if (XLimit > UB_X) break;
                int Answer = NumInfoDict.Count;
                foreach (var EachPair in NumInfoDict) {
                    NumInfo CurrNumInfo = EachPair.Value;
                    bool IsInnerX = false;
                    if (LoopX <= CurrNumInfo.MinX && CurrNumInfo.MaxX <= XLimit) {
                        IsInnerX = true;
                    }
                    bool IsInnerY = false;
                    if (LoopY <= CurrNumInfo.MinY && CurrNumInfo.MaxY <= YLimit) {
                        IsInnerY = true;
                    }

                    if (IsInnerX && IsInnerY) {
                        Answer--;
                    }
                }
                AnswerList.Add(Answer);
            }
            sb.AppendLine(IntEnumJoin(" ", AnswerList));
        }
        Console.Write(sb.ToString());
    }

    // セパレータとInt型の列挙を引数として、結合したstringを返す
    static string IntEnumJoin(string pSeparater, IEnumerable<int> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }

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

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

        SplitAct(StrList[0]);

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

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

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


解説

オセロセットで考察すれば、

□□□□□□□□
□●□□□□□□
□□□□□●□□
□□□□□□●□
□□●□□□□□
□□□□●□□□
□□□□□□□□
□□□□□□□□

数値ごとの
X座標の最小値と最大値
Y座標の最小値と最大値
を持っておき、マスクする矩形で、全て内包できるかを判定すれば良いと分かります。

これは、区間の内包判定問題になります。
3以上6以下の区間を内包する必要十分条件は、
区間開始が3以下であること、かつ、区間終了が6以上であること
となります。
図で考えると分かりやすいです。
     -----------
     3         6