mayoko’s diary

プロコンとかいろいろ。

東京工業大学プログラミングコンテスト2015 G - titech分離

解法

貪欲で解けます。

s を逆から読んでいき, "hcetit" という文字列のうちある部分まで確定している文字列がそれぞれいくつあるかを, state という配列でまとめていきます。
例えば, tititechtech という文字列を考えます(入力例 2 です)。逆から読むと hcethcetitit です。 1 文字目の時点では
h -> 1
hc -> 0
hce -> 0
hcet -> 0
hceti -> 0
hcetit -> 0
となります。 2 文字目まで見ると, c があります。"h" という文字列がある場合には c という文字がくると "hc" まで確定したことになるので,
h -> 0
hc -> 1
hce -> 0
hcet -> 0
hceti -> 0
hcetit -> 0
続けてやっていくと, hcethcet まで読んだ時点では
h -> 0
hc -> 0
hce -> 0
hcet -> 2
hceti -> 0
hcetit -> 0
となります。次に it が来るので,
h -> 0
hc -> 0
hce -> 0
hcet -> 1
hceti -> 0
hcetit -> 1
さらに it が来るので,
h -> 0
hc -> 0
hce -> 0
hcet -> 0
hceti -> 0
hcetit -> 2
となり終わりです。今回は, 余計な文字(titech 以外の文字, 例えば g)がなく, state
の最後以外の数字がすべて 0 で作業が終了したので OK, という感じです。

雰囲気としてはこんな感じですが, titech という文字列の中には, t という文字が 2 箇所に現れるので, hce の後ろの t にするか, hceti の後ろの t にするかを選択しなければならない場面がある可能性があります。しかし, この場合は貪欲に hce の後ろの t にすれば解決です。
なぜかというと, このようにするとこの後に i が来た場合に, hce の後ろの t のカウントを増やしておけば i に対応できる可能性がありますが, hceti の後ろの t のカウントを増やしていると i という文字に対応できない可能性があるからです。 hce の後ろの t のカウントを増やしておけば損はしない, ということですね。

void no() {
    cout << "No" << endl;
    exit(0);
}

int state[6];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    reverse(s.begin(), s.end());
    for (int i = 0; i < n; i++) {
        if (s[i] == 'h') {
            state[0]++;
        } else if (s[i] == 'c') {
            if (state[0] == 0) no();
            else {
                state[0]--;
                state[1]++;
            }
        } else if (s[i] == 'e') {
            if (state[1] == 0) no();
            else {
                state[1]--;
                state[2]++;
            }
        } else if (s[i] == 't') {
            if (state[2] > 0) {
                state[2]--;
                state[3]++;
            } else if (state[4] > 0) {
                state[4]--;
                state[5]++;
            } else no();
        } else if (s[i] == 'i') {
            if (state[3] == 0) no();
            else {
                state[3]--;
                state[4]++;
            }
        } else no();
    }
    for (int i = 0; i < 5; i++) if (state[i]) no();
    cout << "Yes" << endl;
    return 0;
}