ARC148-B dp

問題へのリンク

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("6");
            WillReturn.Add("dpdppd");
            //dddpdd
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("ddd");
            //ddd
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("11");
            WillReturn.Add("ddpdpdppddp");
            //ddddpdpdddp
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        int UB = S.Length - 1;

        var AnswerKouho = new List<string>();
        AnswerKouho.Add(S);
        for (int I = 0; I <= UB; I++) {
            if (S[I] != 'p') continue;
            for (int J = I; J <= UB; J++) {
                string Sub = S.Substring(I, J - I + 1);
                string Answer = S.Remove(I, J - I + 1);
                Answer = Answer.Insert(I, DeriveRev(Sub));
                AnswerKouho.Add(Answer);

                AnswerKouho = AnswerKouho.OrderBy(pX => pX).Take(1).ToList();
            }
            break;
        }
        Console.WriteLine(AnswerKouho.Min());
    }

    // 反転した文字列を返す
    static string DeriveRev(string pStr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = pStr.Length - 1; 0 <= I; I--) {
            if (pStr[I] == 'd') sb.Append('p');
            else sb.Append('d');
        }
        return sb.ToString();
    }
}

解説

変換する区間 [L,R]でありえるものを考えます。
2*2で4通りあります。

場合01 (L,R) = (6,6)
変換すると(9,9)になって損なので
変換候補として不適です。

場合02 (L,R) = (6,9)
変換すると(6,9)になって、意味がなく、
これより狭い区間で良いため、
変換候補として不適です。

場合03 (L,R) = (9,6)
変換すると(6,9)になって、意味があるので、
変換候補になりえます。

場合04 (L,R) = (9,9)
変換すると(6,6)になって、意味があるので、
変換候補になりえます。

以上により、[L,R]の区間で
Lが9の場合のみ変換候補になりえます。

また、9の中で一番左を変換しないのは、損なので
1番左の9のみが区間のLの候補と分かります。