HHKB 2020 E Lamps

問題へのリンク

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("1 5");
            WillReturn.Add("..#..");
            //48
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 3");
            WillReturn.Add("..#");
            WillReturn.Add("#..");
            //52
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 1000000007;
    static long UB_X;
    static long UB_Y;

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[,] BanArr = CreateBanArr(InputList.Skip(1));

        UB_X = BanArr.GetUpperBound(0);
        UB_Y = BanArr.GetUpperBound(1);

        long AllWhiteCnt = 0;
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == '.') AllWhiteCnt++;
            }
        }

        if (AllWhiteCnt == 0) {
            Console.WriteLine(0);
            return;
        }

        // 2べきの配列
        long BekiVal = 1;
        long[] BekiArr = new long[AllWhiteCnt + 1];
        for (long I = 1; I <= BekiArr.GetUpperBound(0); I++) {
            BekiVal *= 2;
            BekiVal %= Hou;
            BekiArr[I] = BekiVal;
        }

        long[,] RunSumArr = new long[UB_X + 1, UB_Y + 1];

        // 横方向の累積和(左から右)
        for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
            long CurrSum = 0;
            for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
                if (BanArr[LoopX, LoopY] == '#') CurrSum = 0;
                if (BanArr[LoopX, LoopY] == '.') CurrSum++;
                RunSumArr[LoopX, LoopY] += CurrSum;
            }
        }

        // 横方向の累積和(右から左)
        for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
            long CurrSum = 0;
            for (long LoopX = UB_X; 0 <= LoopX; LoopX--) {
                if (BanArr[LoopX, LoopY] == '#') CurrSum = 0;
                if (BanArr[LoopX, LoopY] == '.') CurrSum++;
                RunSumArr[LoopX, LoopY] += CurrSum;
            }
        }

        // 縦方向の累積和(下から上)
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            long CurrSum = 0;
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == '#') CurrSum = 0;
                if (BanArr[LoopX, LoopY] == '.') CurrSum++;
                RunSumArr[LoopX, LoopY] += CurrSum;
            }
        }

        // 縦方向の累積和(上から下)
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            long CurrSum = 0;
            for (long LoopY = UB_Y; 0 <= LoopY; LoopY--) {
                if (BanArr[LoopX, LoopY] == '#') CurrSum = 0;
                if (BanArr[LoopX, LoopY] == '.') CurrSum++;
                RunSumArr[LoopX, LoopY] += CurrSum;
            }
        }

        // 重複カウントしているので、3を引く
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == '.') {
                    RunSumArr[LoopX, LoopY] -= 3;
                }
            }
        }

        long Answer = 0;
        for (long LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (long LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (BanArr[LoopX, LoopY] == '#') continue;

                long CurrCnt = RunSumArr[LoopX, LoopY];
                long RestCnt = AllWhiteCnt - CurrCnt;

                long CurrPattern = BekiArr[CurrCnt] - 1;
                if (RestCnt > 0) {
                    CurrPattern *= BekiArr[RestCnt];
                    CurrPattern %= Hou;
                }
                Answer += CurrPattern;
                Answer %= Hou;
            }
        }
        if (Answer < 0) Answer += Hou;
        Console.WriteLine(Answer);
    }

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

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

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

解説

全ての配置での照らされるマス
の、のべ合計なので

マス目ごとに照らすことができる場合の数の
総合計を求めれば良いです。

●横方向の累積和(左から右)
●横方向の累積和(右から左)
●縦方向の累積和(下から上)
●縦方向の累積和(上から下)
の4つの累積和を最初に求めておけば、
マス目ごとに照らすことができる場合の数
を高速に求めることができます。