Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 282 C問題 String Delimiter

AtCoder ABC282 ABC C問題 300 pts

問題

提出解答

問題の概要

英小文字, ${\tt "}, {\tt ,}$ からなる長さ $N$ の文字列 $S$ が与えられる. なお, $S$ にある ${\tt "}$ の個数は偶数である.

$S$ に含まれる ${\tt "}$ の数を $2K$ とする. 各 $i=1,2, \dots, K$ に対して, $(2i-1)$ 番目の ${\tt "}$ と $2i$ 番目の ${\tt "}$ の間にある文字を括られた文字という.

$S$ の括られた文字ではない ${\tt ,}$ を全て ${\tt .}$ に置き換えた文字列を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$S$ は英小文字, ${\tt "}, {\tt ,}$ からなる長さ $N$ の文字列
$S$ に含まれる ${\tt "}$ の数は偶数個

解法

次のようにして正解の文字列を得ることができる.

${\rm mode} \gets 0$ とする.
の順に以下を行う.
- $S_i={\tt "}$ ならば, ${\rm mode}$ の $0,1$ を切り替える.
- $S_i={\tt ,}$ かつ, ${\rm mode}=1$ ならば, $S_i \gets {\tt .}$ とする.
$S$ が解答である.