Kazun の競プロ記録

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

AtCoder Beginner Contest 286 B問題 Cat

AtCoder ABC286 ABC B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法1
解法2
解法3

問題

提出解答

(解法 1)

(解法 2)

Submission #38191181 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

(解法 3)

Submission #38191181 - UL Systems Programming Contest 2023(AtCoder Beginner Contest 286)

問題の概要

長さ $N$ の英小文字列 $S$ に対して, 以下を実行して得られる英小文字列を求めよ.

$S$ に連続して含まれる ${\tt na}$ を全て ${\tt nya}$ に置き換える.

制約

$1 \leq N \leq 1000$
$S$ は英小文字列

解法1

$i=N-1, N-2, \dots, 1$ の順に以下を実行して得られる文字列が答えである.

$S_i={\tt n}, S_{i+1}={\tt a}$ ならば, $i$ 文字目と [tex (i+1)] 文字目の間に ${\tt y}$ を挿入する.

解法2

Stack というデータ構造を頭に入れることで, 次のようにしても解くことができる (実はこの解法が一番高速である).

$T$ を空文字列とする.
の順に以下を実行する.
- $T$ の末尾に $S_i$ を追加する.
- $T$ の長さが $2$ 以上で, $T$ の末尾 $2$ 文字が ${\tt na}$ ならば, $T$ の末尾 $2$ 文字を削除し, $T$ の末尾に ${\tt nya}$ を追加する.
$T$ が答えである.

解法3

言語によっては文字列 $X$ に含まれている $A$ を全て $B$ に変えるという関数が用意されている場合があるので, それを利用することもできる.