ARC081-E Don't Be a Subsequence

問題へのリンク

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("atcoderregularcontest");
            //b
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("abcdefghijklmnopqrstuvwxyz");
            //aa
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn");
            //aca
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static List<string> mAnswerKouhoList = new List<string>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        Console.WriteLine(Solve(S));
    }

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

        var CharList = new List<char>();
        for (char I = 'a'; I <= 'z'; I++) CharList.Add(I);

        // (最小文字数で)辞書順最小の文字列 [最初の文字] なDP表
        var PrevDP = new Dictionary<char, string>();

        foreach (char EachChar in CharList) {
            if (pS[UB] == EachChar) {
                PrevDP[EachChar] = EachChar + "a";
            }
            else {
                PrevDP[EachChar] = EachChar.ToString();
            }
        }

        for (int I = UB - 1; 0 <= I; I--) {
            var CurrDP = new Dictionary<char, string>();
            foreach (char EachChar in CharList) {
                if (pS[I] == EachChar) {
                    var Item = PrevDP.OrderBy(pX => pX.Value.Length).ThenBy(pX => pX.Key).First();
                    CurrDP[EachChar] = EachChar + Item.Value;
                }
                else {
                    CurrDP[EachChar] = PrevDP[EachChar];
                }
            }
            PrevDP = CurrDP;
        }
        return PrevDP.OrderBy(pX => pX.Value.Length).ThenBy(pX => pX.Key).First().Value;
    }
}

解説

(最小文字数で)辞書順最小の文字列 [最初の文字] なDP表
を文字列の後ろからのDPで更新してます。