ABC442-F Diagonal Separation 2

問題へのリンク

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

    static int[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => int.Parse(pX)).ToArray();
    }

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

        // 黒マスの数[X座標]な配列
        int AllBlackCnt = 0;
        var BlackCntArr = new int[UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (BanArr[X, Y] == '#') {
                    BlackCntArr[X]++;
                    AllBlackCnt++;
                }
            }
        }

        // 黒マスの数[X座標]の累積和
        int[] BlackCntRunSumArr = (int[])BlackCntArr.Clone();
        for (int X = 1; X <= UB; X++) {
            BlackCntRunSumArr[X] += BlackCntRunSumArr[X - 1];
        }

        // 未登場なY座標のSet[X座標]な配列
        HashSet<int> NonAppearYSet = new HashSet<int>();
        for (int Y = 0; Y <= UB; Y++) {
            NonAppearYSet.Add(Y);
        }

        // 初登場のY座標のSet[X座標]な配列
        HashSet<int>[] YSetArr = new HashSet<int>[UB + 1];
        for (int X = 0; X <= UB; X++) {
            YSetArr[X] = new HashSet<int>();
            foreach (int Y in NonAppearYSet) {
                if (BanArr[X, Y] == '#') {
                    YSetArr[X].Add(Y);
                }
            }
            NonAppearYSet.ExceptWith(YSetArr[X]);
        }

        // その黒マスが階段の最上マスの時のコスト[X,Y]なインラインDP表
        int[,] DPArr = new int[UB + 1, UB + 1];
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                DPArr[LoopX, LoopY] = int.MaxValue;
            }
        }

        var NewYSet = new HashSet<int>();
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            NewYSet.UnionWith(YSetArr[LoopX]);

            // 最小コスト[遷移先Y座標]
            int[] RunMinArr = new int[UB + 1];
            if (LoopX > 0) {
                int CurrMin = BlackCntRunSumArr[LoopX - 1];
                for (int LoopY = UB; 0 <= LoopY; LoopY--) {
                    CurrMin = Math.Min(CurrMin, DPArr[LoopX - 1, LoopY]);
                    RunMinArr[LoopY] = CurrMin;
                }
            }

            // このX座標で、縦方向の黒マス数の累積和
            int RunSumBlackCnt = 0;

            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (BanArr[LoopX, LoopY] == '#') {
                    RunSumBlackCnt++;
                }

                if (NewYSet.Contains(LoopY)) {
                    int BlackCnt1 = RunSumBlackCnt;
                    if (BanArr[LoopX, LoopY] == '#') {
                        BlackCnt1--;
                    }
                    int Cost1 = BlackCnt1;

                    int BlackCnt2 = BlackCntArr[LoopX] - BlackCnt1;

                    int Cost2 = UB - LoopY + 1;
                    Cost2 -= BlackCnt2;
                    DPArr[LoopX, LoopY] = RunMinArr[LoopY] + Cost1 + Cost2;
                }
            }
        }

        long Answer = AllBlackCnt;
        for (int LoopY = 0; LoopY <= UB; LoopY++) {
            Answer = Math.Min(Answer, DPArr[UB, LoopY]);
        }
        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;
    }
}

解説

ダイソーのオセロセットで考察します。
黒マスの階段を作成する最小コストを求める問題だと分かります。

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

全ての黒マスを白マスに変更するのが、解候補だと分かります。
左から見て、何列かを全て白マスに変更し、
いずれかの黒マスから黒階段を作成し始めるのも、解候補だと分かります。

なので、その黒マスが階段の最上マスの時のコスト[X,Y]なインラインDP表
を更新していけば、解を求めることができます。

遷移を高速化するために、DPで使うデータの事前準備も行ってます。