C - Debug

Contest Duration: 2025-02-22(Sat) 12:00 - 2025-02-22(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Debug Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

英大文字のみからなる文字列 $S$ が与えられます。
$S$ に対して、次の手順を行った後に得られる文字列を出力してください。

文字列が WA を（連続する）部分文字列として含む限り、次の操作を繰り返す。

文字列中に登場する WA のうち最も先頭のものを AC に置換する。

なお、本問題の制約下で、この操作は高々有限回しか繰り返されないことが証明できます。

制約

$S$ は長さ $1$ 以上 $3\times 10^5$ 以下の英大文字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

$S$ に対して、問題文中に記された手順を行った後に得られる文字列を出力せよ。

入力例 1Copy

Copy

WACWA

出力例 1Copy

Copy

ACCAC

最初、文字列は $S=$ WACWA です。
この文字列には $1$ 文字目から $2$ 文字目、および、 $4$ 文字目から $5$ 文字目の $2$ ヶ所に WA が部分文字列として含まれています。
$1$ 回目の操作では、そのうち先頭のもの、すなわち $1$ 文字目から $2$ 文字目の部分を AC に置換し、文字列は ACCWA となります。
$1$ 回目の操作後の文字列には $4$ 文字目から $5$ 文字目の $1$ ヶ所にのみ WA が部分文字列として含まれているため、 $2$ 回目の操作ではこれを AC に置換し、文字列は ACCAC となります。
ACCAC は WA を部分文字列として含まないため、手順は終了します。よって、ACCAC を出力します。

入力例 2Copy

Copy

WWA

出力例 2Copy

Copy

ACC

最初、文字列は $S=$ WWA です。
この文字列には $2$ 文字目から $3$ 文字目の $1$ ヶ所にのみ WA が部分文字列として含まれているため、 $1$ 回目の操作ではこれを AC に置換し、文字列は WAC となります。
次に、 $1$ 回目の操作後の文字列は $1$ 文字目から $2$ 文字目の $1$ ヶ所にのみ WA が部分文字列として含まれているため、 $2$ 回目の操作ではこれを AC に置換し、文字列は ACC となります。
ACC は WA を部分文字列として含まないため、手順は終了します。よって、ACC を出力します。

入力例 3Copy

Copy

WWWWW

出力例 3Copy

Copy

WWWWW

$S$ には最初から WA が部分文字列として含まれてないため、操作は $1$ 回も行われず手順は終了します。よって、WWWWW を出力します。

Score : $300$ points

Problem Statement

You are given a string $S$ consisting of uppercase English letters.
Apply the following procedure to $S$ , and then output the resulting string:

As long as the string contains WA as a (contiguous) substring, repeat the following operation:

Among all occurrences of WA in the string, replace the leftmost one with AC.

It can be proved under the constraints of this problem that this operation is repeated at most a finite number of times.

Constraints

$S$ is a string of uppercase English letters with length between 1 and $3\times 10^5$ , inclusive.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print the resulting string after performing the procedure described in the problem statement on $S$ .

Sample Input 1Copy

Copy

WACWA

Sample Output 1Copy

Copy

ACCAC

Initially, the string is $S=$ WACWA.
This string contains WA as a substring in two places: from the 1st to the 2nd character, and from the 4th to the 5th character.
In the first operation, we replace the leftmost occurrence (the substring from the 1st to the 2nd character) with AC, resulting in ACCWA.
After the first operation, the string contains WA as a substring in exactly one place: from the 4th to the 5th character.
In the second operation, we replace it with AC, resulting in ACCAC.
Since ACCAC does not contain WA as a substring, the procedure ends. Therefore, we output ACCAC.

Sample Input 2Copy

Copy

WWA

Sample Output 2Copy

Copy

ACC

Initially, the string is $S=$ WWA.
This string contains WA as a substring in exactly one place: from the 2nd to the 3rd character.
In the first operation, we replace it with AC, resulting in WAC.
Then, after the first operation, the string contains WA in exactly one place: from the 1st to the 2nd character.
In the second operation, we replace it with AC, resulting in ACC.
Since ACC does not contain WA as a substring, the procedure ends. Therefore, we output ACC.

Sample Input 3Copy

Copy

WWWWW

Sample Output 3Copy

Copy

WWWWW

Since $S$ does not contain WA as a substring from the start, no operations are performed and the procedure ends immediately. Therefore, we output WWWWW.