ABC086-D Checker

問題へのリンク

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("4 3");
            WillReturn.Add("0 1 W");
            WillReturn.Add("1 2 W");
            WillReturn.Add("5 3 B");
            WillReturn.Add("5 4 B");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1000");
            WillReturn.Add("0 0 B");
            WillReturn.Add("0 1 W");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 2");
            WillReturn.Add("1 2 B");
            WillReturn.Add("2 1 W");
            WillReturn.Add("2 2 B");
            WillReturn.Add("1 0 B");
            WillReturn.Add("0 6 W");
            WillReturn.Add("4 5 W");
            //4
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long UB;
    static Dictionary<long, long> mWhitePosCntDict = new Dictionary<long, long>();

    static long[,] mRunSumArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        mK = wkArr[1];
        UB = 2 * mK - 1;

        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');
            long X = long.Parse(SplitArr[0]);
            long Y = long.Parse(SplitArr[1]);
            if (SplitArr[2] == "B") {
                X += mK;
            }
            X %= 2 * mK;
            Y %= 2 * mK;

            long Hash = GetHash(X, Y);
            if (mWhitePosCntDict.ContainsKey(Hash) == false) {
                mWhitePosCntDict[Hash] = 0;
            }
            mWhitePosCntDict[Hash]++;
        }

        // 2次元累積和を求める
        mRunSumArr = CreateRunSumArr();

        long Answer = long.MinValue;
        for (long LoopX = 0; LoopX <= UB; LoopX++) {
            for (long LoopY = 0; LoopY <= UB; LoopY++) {

                var ResultList = new List<long>();

                // 2つ分の変位ベクトルを加算した始点
                ResultList.Add(DeriveSatisfyCnt(LoopX, LoopY - 2 * mK));
                ResultList.Add(DeriveSatisfyCnt(LoopX, LoopY + 2 * mK));
                ResultList.Add(DeriveSatisfyCnt(LoopX - 2 * mK, LoopY));
                ResultList.Add(DeriveSatisfyCnt(LoopX + 2 * mK, LoopY));

                // 45度、135度、215度、305度の4つの変位ベクトルを加算した始点
                ResultList.Add(DeriveSatisfyCnt(LoopX, LoopY));
                ResultList.Add(DeriveSatisfyCnt(LoopX - mK, LoopY - mK));
                ResultList.Add(DeriveSatisfyCnt(LoopX - mK, LoopY + mK));
                ResultList.Add(DeriveSatisfyCnt(LoopX + mK, LoopY - mK));
                ResultList.Add(DeriveSatisfyCnt(LoopX + mK, LoopY + mK));

                long AnswerKouho = ResultList.Sum();
                Answer = Math.Max(Answer, AnswerKouho);
            }
        }
        Console.WriteLine(Answer);
    }

    // 座標のハッシュ値を返す
    static long GetHash(long pX, long pY)
    {
        return pX * 10000000000 + pY;
    }

    // 黒マスにしたいマスに1、白マスにしたいマスに0を設定した、二次元配列を作成し、
    // 右方向と、下方向の、累積和を設定して、返す
    static long[,] CreateRunSumArr()
    {
        long[,] RunSumArr = new long[UB + 1, UB + 1];
        for (long LoopX = 0; LoopX <= UB; LoopX++) {
            for (long LoopY = 0; LoopY <= UB; LoopY++) {
                long Hash = GetHash(LoopX, LoopY);
                if (mWhitePosCntDict.ContainsKey(Hash)) {
                    RunSumArr[LoopX, LoopY] = mWhitePosCntDict[Hash];
                }
            }
        }

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

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

        return RunSumArr;
    }

    // 黒い正方形の左上座標を引数として、要望を満たす数を返す
    static long DeriveSatisfyCnt(long pBaseX, long pBaseY)
    {
        if (UB < pBaseX) return 0;
        if (UB < pBaseY) return 0;

        long RangeX = pBaseX + mK - 1;
        long RangeY = pBaseY + mK - 1;

        if (RangeX < 0) return 0;
        if (RangeY < 0) return 0;

        pBaseX = Math.Max(pBaseX, 0);
        pBaseY = Math.Max(pBaseY, 0);

        RangeX = Math.Min(RangeX, UB);
        RangeY = Math.Min(RangeY, UB);

        long CurrSumCnt = DeriveSumRect(RangeX, RangeY);
        CurrSumCnt -= DeriveSumRect(pBaseX - 1, RangeY);
        CurrSumCnt -= DeriveSumRect(RangeX, pBaseY - 1);
        CurrSumCnt += DeriveSumRect(pBaseX - 1, pBaseY - 1);

        return CurrSumCnt;
    }

    // (0,0)と(pX,pY)からなる長方形の数の和を返す
    static long DeriveSumRect(long pX, long pY)
    {
        if (pX < 0) return 0;
        if (pY < 0) return 0;
        return mRunSumArr[pX, pY];
    }
}

解説

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

という入力について考えると
2マスごとに白と黒が変わるので
1 2 Bという要望は、X座標に2を足して
3 2 Wという要望だと考えることができます。

また、4マスごとに白と黒を繰り返すので
座標はmod4で考えることができます。

以上をふまえて、マス目ごとに、
ここを白にしたら満たす要望の数を設定して、二次元累積和を求めておき、
どのマスを起点にして、白の正方形を設定するかを
全探索してます。

オセロセットで考察すると
□●●●□□
□●●●□□
●□□□●●
●□□□●●
●□□□●●
□●●●□□
のような場合があるので、
2つ分の変位ベクトルを加算した始点
45度、135度、215度、305度の4つの変位ベクトルを加算した始点
からも満たす要望の数を調べる必要があります。