けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 108 B - Abbreviate Fox (3Q, 茶色, 400 点)

カッコ列系の問題!

問題概要

長さ  N の文字列  S が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。

  • 文字列中の "fox" を削除する

制約

  •  1 \le N \le 2 \times 10^{5}

考えたこと

カッコ列でよく似た問題はすごく有名。

()((()()))(())))))(((((())()(

のようなカッコ列が与えられて、"()" の部分を削除していくことで出来上がる文字列の文字数は、以下のようにして求めることができる。

  • 空のスタックを用意して、カッコ列を左から順に次のように処理する
  • "(" が来たら、それをスタックの末尾に push する
  • ")" が来たら、
    • スタックの末尾が "(" ならば、それを pop する (")" も push しない)
    • スタックの末尾が ")" ならば、スタックに ")" を push する

そして最後にスタックに残るものが、「最終的にできあがる文字列」ということになる。次のやつがまさにその問題。

atcoder.jp

他にも、このような考え方で解ける問題として、「カッコ列が整合しているかどうかを判定せよ」という問題がすごく有名!!!

今回の問題の場合

今回の問題も大体一緒。カッコ列の "()" が "fox" になっただけ。3 文字になっただけ。

計算量は  O(N) になる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S;
    cin >> N >> S;
    string res = "";
    for (auto c : S) {
        if (c == 'x' && res.size() >= 2 && res.substr(res.size()-2) == "fo") {
            res.pop_back(), res.pop_back();
        }
        else res += c;
    }
    cout << res.size() << endl;
}