[ARC136A] A ↔ BB

ID: 19748

远端评测题

2000ms

1024MiB

难度: (无)

上传者:

配点 : $300$ 点

問題文

A, B, C からなる長さ $N$ の文字列 $S$ が与えられます．

あなたは， $S$ に対して以下の $2$ 種類の操作を好きな順序で好きな回数行うことができます．

操作を終えたあとの $S$ としてあり得る文字列のうち，辞書順最小のものを求めてください．

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 $S$ と文字列 $T$ の大小を判定するアルゴリズムを以下に説明します。

以下では $S$ の $i$ 文字目の文字を $S_i$ のように表します。また、 $S$ が $T$ より辞書順で小さい場合は $S \lt T$ 、大きい場合は $S \gt T$ と表します。

$S$ と $T$ のうち長さが短い方の文字列の長さを $L$ とします。 $i=1,2,\dots,L$ に対して $S_i$ と $T_i$ が一致するか調べます。
$S_i \neq T_i$ である $i$ が存在する場合、そのような $i$ のうち最小のものを $j$ とします。そして、 $S_j$ と $T_j$ を比較して、 $S_j$ がアルファベット順で $T_j$ より小さい場合は $S \lt T$ 、大きい場合は $S \gt T$ と決定して、アルゴリズムを終了します。
$S_i \neq T_i$ である $i$ が存在しない場合、 $S$ と $T$ の長さを比較して、 $S$ が $T$ より短い場合は $S \lt T$ 、長い場合は $S \gt T$ と決定して、アルゴリズムを終了します。

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

$N$

$S$

答えを出力せよ．

4
CBAA

CAAB

以下のように操作すればよいです．

$S$ を CAAB より辞書順で小さい文字列にすることはできません．よって答えは CAAB になります．

1
A

一度も操作を行いません．

6
BBBCBB

ABCA