第5回PAST L T消し

問題へのリンク

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("7");
            WillReturn.Add("adbabcd");
            WillReturn.Add("abc");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            WillReturn.Add("ababaa");
            WillReturn.Add("aba");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6");
            WillReturn.Add("zzzzzz");
            WillReturn.Add("abc");
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        string T = InputList[2];
        int Result = Solve(S, T);
        Console.WriteLine(Result);
    }

    static int Solve(string pS, string pT)
    {
        int UB = pS.Length - 1;

        // 除去可否[区間Sta , 区間End] なDP表
        int[,] RangeDPArr = new int[UB + 1, UB + 1];

        // 幅でループ
        for (int LoopWidth = 3; LoopWidth <= pS.Length; LoopWidth += 3) {
            // 区間Staでループ
            for (int LoopStaInd = 0; LoopStaInd <= UB; LoopStaInd++) {
                int EndInd = LoopStaInd + LoopWidth - 1;
                if (EndInd > UB) break;

                // 幅が3の場合
                if (LoopWidth == 3) {
                    if (pS.Substring(LoopStaInd, 3) == pT) {
                        RangeDPArr[LoopStaInd, EndInd] = 1;
                    }
                }

                // 幅が6以上の場合
                if (LoopWidth >= 6) {
                    bool IsOK = false;

                    if (pS[LoopStaInd] == pT[0] && pS[EndInd] == pT[2]) {
                        for (int I = LoopStaInd + 1; I <= EndInd - 1; I += 3) {
                            if (pS[I] != pT[1]) continue;

                            // 左に区間がある場合
                            if (LoopStaInd + 1 < I) {
                                int LeftInd = LoopStaInd + 1;
                                int RightInd = I - 1;
                                if (RangeDPArr[LeftInd, RightInd] == 0) {
                                    continue;
                                }
                            }
                            // 右に区間がある場合
                            if (I < EndInd - 1) {
                                int LeftInd = I + 1;
                                int RightInd = EndInd - 1;
                                if (RangeDPArr[LeftInd, RightInd] == 0) {
                                    continue;
                                }
                            }
                            IsOK = true;
                            break;
                        }
                    }

                    if (IsOK == false) {
                        for (int LoopMid = LoopStaInd + 2; LoopMid <= EndInd - 3; LoopMid += 3) {
                            if (RangeDPArr[LoopStaInd, LoopMid] == 1 &&
                                RangeDPArr[LoopMid + 1, EndInd] == 1) {
                                IsOK = true;
                                break;
                            }
                        }
                    }
                    if (IsOK) {
                        RangeDPArr[LoopStaInd, EndInd] = 1;
                    }
                }
            }
        }

        int Result = ExecDP(RangeDPArr, UB);
        return Result;
    }

    // 閉区間の定義
    struct RangeInfoDef
    {
        internal int Sta;
        internal int End;
    }

    // DPで最大の除去回数を求める
    static int ExecDP(int[,] pRangeDPArr, int UB)
    {
        var RangeInfoList = new List<RangeInfoDef>();
        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= UB; J++) {
                if (pRangeDPArr[I, J] == 1) {
                    RangeInfoDef WillAdd;
                    WillAdd.Sta = I;
                    WillAdd.End = J;
                    RangeInfoList.Add(WillAdd);
                }
            }
        }

        // 最大の除去回数[現在位置]なDP表
        int?[] DPArr = new int?[UB + 2];
        DPArr[0] = 0;

        for (int I = 0; I <= UB + 1; I++) {
            if (DPArr[I].HasValue == false) continue;

            foreach (RangeInfoDef EachRangeInfo in RangeInfoList) {
                if (EachRangeInfo.Sta != I) continue;
                int EndInd = EachRangeInfo.End + 1;
                int Range = EndInd - I + 1;
                int NewVal = DPArr[I].Value + Range / 3;
                if (DPArr[EndInd].HasValue == false || DPArr[EndInd] < NewVal) {
                    DPArr[EndInd] = NewVal;
                }
            }

            int NextInd = I + 1;
            if (NextInd > UB) break;
            if (DPArr[NextInd].HasValue == false || DPArr[NextInd] < DPArr[I]) {
                DPArr[NextInd] = DPArr[I];
            }
        }
        return DPArr.Max().Value;
    }
}

解説

除去可否[区間Sta , 区間End] なDP表 を作成してから、
最大の除去回数[現在位置]なDP表 を作成してます。

類題

TDP I イウィ