東工大プロコン2015 G titech分離

■■■問題■■■

英小文字(a-z)からなる文字列Sが与えられる。
Sをいくつかの(連続とは限らない)部分文字列に分解する。
つまり、Sの各文字がちょうど1つの部分文字列に含まれるように、Sから複数の部分文字列を選ぶ。

分解した結果の部分文字列が全てtitechになるような分解方法があるかどうか判定せよ。

■■■入力■■■

S

1行目に文字列S(1 <= |S| <= 100)が与えられる。

■■■出力■■■

分解が可能ならYes、不可能ならNoを出力せよ。出力の末尾に改行を入れること。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("titech");
            //Yes
            //1つのtitechに分解できる
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("tititechtech");
            //Yes
            //例えば、1,2,5,6,7,8文字目と3,4,9,10,11,12文字目に分解すれば2つのtitechに分解できる
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("titecg");
            //No
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("tttiiittteeeccchhh");
            //Yes
            //3つのtitechに分解できる
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        Console.WriteLine(Solve(InputList[0]));
    }

    static string Solve(string pTarget)
    {
        //余計な文字の有無をチェック
        int CntT = pTarget.Count(X => X == 't');
        int CntI = pTarget.Count(X => X == 'i');
        int CntE = pTarget.Count(X => X == 'e');
        int CntC = pTarget.Count(X => X == 'c');
        int CntH = pTarget.Count(X => X == 'h');

        if (pTarget.Length != CntT + CntI + CntE + CntC + CntH) return "No";
        if (CntT != CntI * 2) return "No";
        if (CntT != CntC * 2) return "No";
        if (CntT != CntE * 2) return "No";
        if (CntT != CntH * 2) return "No";
        int AutoMatonCnt = CntT / 2;

        int[] AutoMatonArr = new int[AutoMatonCnt];
        for (int I = 0; I <= AutoMatonArr.GetUpperBound(0); I++) {
            AutoMatonArr[I] = -1;
        }

        Action<int> wkAct = pCurrJyoutai =>
        {
            //最後のtは、次にt待ちのeがないとき限定で受理
            if (pCurrJyoutai == 4) {
                if (AutoMatonArr.Contains(2))
                    return;
            }

            int wkInd = Array.IndexOf(AutoMatonArr, pCurrJyoutai);
            if (wkInd < 0) return;
            AutoMatonArr[wkInd]++;
        };

        //オートマトンは-1が初期状態で
        //下記の状態番号に遷移する
        //hcetit
        //012345
        for (int I = pTarget.Length - 1; 0 <= I; I--) {
            char CurrStr = pTarget[I];
            if (CurrStr == 'h') wkAct(-1);
            if (CurrStr == 'c') wkAct(0);
            if (CurrStr == 'e') wkAct(1);
            if (CurrStr == 't') wkAct(2);
            if (CurrStr == 'i') wkAct(3);
            if (CurrStr == 't') wkAct(4);
        }
        return Array.TrueForAll(AutoMatonArr, X => X == 5) ? "Yes" : "No";
    }
}

解説

titechを受理するオートマトンを何個か用意して
正順に文字列を見ていくと、バックトラックが必要だと思いますが、

hcetitを受理するオートマトンを何個か用意して
逆順に文字列を見ていくと、貪欲法が使えます。
(最後のtは、次にt待ちのeがないとき限定で受理とできるため)