ABC185-E Sequence Matching

問題へのリンク

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        int[] BArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        int UB_A = AArr.GetUpperBound(0) + 1;
        int UB_B = BArr.GetUpperBound(0) + 1;

        // 最小コスト[カレントのAの添字 , カレントのBの添字]なDP表
        int?[,] DPArr = new int?[UB_A + 1, UB_B + 1];
        DPArr[0, 0] = 0;

        for (int I = 0; I <= UB_A; I++) {
            for (int J = 0; J <= UB_B; J++) {
                if (DPArr[I, J].HasValue == false) continue;

                Action<int, int, int> UpdateAct = (pNewI, pNewJ, pNewVal) =>
                {
                    if (pNewI > UB_A) return;
                    if (pNewJ > UB_B) return;

                    if (DPArr[pNewI, pNewJ].HasValue) {
                        if (DPArr[pNewI, pNewJ] <= pNewVal) {
                            return;
                        }
                    }
                    DPArr[pNewI, pNewJ] = pNewVal;
                };

                // 一致してる場合
                if (I <= UB_A - 1 && J <= UB_B - 1 && AArr[I] == BArr[J]) {
                    UpdateAct(I + 1, J + 1, DPArr[I, J].Value);
                    continue;
                }

                // Aを進める場合
                UpdateAct(I + 1, J, DPArr[I, J].Value + 1);

                // Bを進める場合
                UpdateAct(I, J + 1, DPArr[I, J].Value + 1);

                // 両方とも進める場合
                UpdateAct(I + 1, J + 1, DPArr[I, J].Value + 1);
            }
        }
        Console.WriteLine(DPArr[UB_A, UB_B]);
    }
}

解説

最小コスト[カレントのAの添字 , カレントのBの添字]なDP表
を更新してます。

AとBが一致してる場合は、
●コスト0で両方進める

AとBが一致してない場合は、
●コスト1で両方進める
●コスト1でAだけ添字を進める
●コスト1でBだけ添字を進める
の3択になります。

DPの計算量は、状態数*遷移数で
1000*1000*3 = 3000000
なので間に合います。