As Simple as One and Two [Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) A]

https://codeforces.com/contest/1276/problem/A

解説

https://codeforces.com/contest/1276/submission/66871311

DPをして復元しよう。
dp[i][t] := i文字目まで処理が終わっていて状態がtのときの削除の最小値
状態のtは今までの文字列の末尾を指していて、「なんでもいい」「O」「ON」「T」「TW」のいずれかである。
この辺を数値化して遷移していけばいい。
これは人力でやると大変だし、抜けもあるので、Aho Corasick法を使うと良い。
下手に頑張るよりアルゴリズムの力を借りよう。
あとは、復元も求められているので、pre[i][t]を用意して、前の状態を保存しておけば復元できる。

TLを見ると貪欲法もある。

string S;
AhoCorasick ac;
//---------------------------------------------------------------------------------------------------
int dp[201010][10];
pair<int, int> pre[201010][10];
void solve() {
    cin >> S;
    int N = S.length();
    rep(i, 0, N + 1) rep(t, 0, 10) dp[i][t] = inf;
    dp[0][ac.root] = 0;
    rep(i, 0, N) rep(t, 0, 10) if(dp[i][t] < inf) {
        if (chmin(dp[i + 1][t], dp[i][t] + 1)) {
            pre[i + 1][t] = { i, t };
        }

        int t2 = ac.next(t, S[i]);
        if (!ac.correct[t2]) {
            if (chmin(dp[i + 1][t2], dp[i][t])) {
                pre[i + 1][t2] = { i, t };
            }
        }
    }

    int ans1 = inf;
    int st = -1;
    rep(t, 0, ac.nodes.size()) if(!ac.correct[t]) {
        if (chmin(ans1, dp[N][t])) st = t;
    }
    printf("%d\n", ans1);
    vector<int> ans2;
    rrep(i, N, 1) {
        int st2 = pre[i][st].second;
        if (dp[i - 1][st2] != dp[i][st]) ans2.push_back(i);
        st = st2;
    }
    rep(i, 0, ans1) {
        if (i) printf(" ");
        printf("%d", ans2[i]);
    }
    printf("\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    ac.add("one");
    ac.add("two");
    ac.build();

    int TT; cin >> TT;
    rep(t, 0, TT) solve();
}