【AtCoder】ABC 394 C - Debug | 緑コーダーが解くAtCoder

atcoder.jp

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 161

問題概要
制約
考察
実装例
コメント

問題概要

英大文字のみからなる文字列 $S$ が与えられるので、 $S$ に対して、次の手順を行った後に得られる文字列を出力せよ。

文字列がWAを部分文字列として含む限り、次の操作を繰り返す。
- 文字列中に登場するWAのうち最も先頭のものをACに置換する。

制約

$S$ の長さは $1$ 以上 $3\times 10^5$ 以下。

考察

基本的には、「 $S$ の先頭から1文字ずつ見ていって、直近の2文字がWAであればACに置き換える」とすればよい。

しかし、サンプルケース2のように、 $S$ の $i$ 文字目にWが存在する場合、 $i+1$ 文字目と $i+2$ 文字目にまたがるWAをACに置き換えた後、連鎖的に置き換えが発生することに注意する必要がある。

ということで、stackと再帰関数を用いて実装していく。具体的なアルゴリズムは以下の通り。

空のstackを用意する。
再帰関数を以下のように定義する。
1. もしstackが空なら、そのまま $c$ を追加して終了。
2. もしstackの先頭がWかつ $c =$ Aならば、先頭要素をpopした後 $f($ A $)$ と $f($ C $)$ を実行して終了。
3. それ以外のとき、そのまま $c$ を追加して終了。
$f(S_i) \: (i = 1, 2, \cdots, N)$ を順に実行する。

実装例

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

void f(stack<char> &st, char c)
{
    if (st.empty())
    {
        st.push(c);
        return;
    }

    if (st.top() == 'W' && c == 'A')
    {
        st.pop();
        f(st, 'A');
        f(st, 'C');
        return;
    }

    st.push(c);
    return;
}

int main()
{
    string S;
    cin >> S;

    stack<char> st;
    rep(i, 0, S.size())
    {
        f(st, S[i]);
    }

    string ans = "";
    while (!st.empty())
    {
        ans += st.top();
        st.pop();
    }
    reverse(all(ans));
    cout << ans << endl;

    return 0;
}