No.1894 Delete AB
タグ : / 解いたユーザー数 125
作問者 :
Shirotsume
/ テスター :
Kanten4205
👑 
ygussany
問題文
A, B からなる長さ $N$ の文字列 $S$ が与えられます。
$S$ に対して以下の操作を $0$ 回以上行ってできる文字列のうち、辞書順で最大のものを求めてください。
- $S$ に含まれる連続部分文字列
ABのうち、好きなものを選んで消去する。その後、残った文字列を順序を保ったまま結合する。
$T$ 個のテストケースが与えられるので、それぞれについて解いてください。
辞書順とは（クリックで展開）
$2$ つの相異なる文字列 $X, \ Y$ が与えられたとき、 $X$ と $Y$ の辞書順による大小は以下のように決まります。$X$ の $i$ 文字目を $X_i$ のように表します。
- $X$ と $Y$ のうち、長さが短い方の文字列の長さを $L$ とする。
- $X_i \neq Y_i$ なる $i$ $(1 \leq i \leq L)$ が存在するならば、そのうち最小の $i$ を $j$ とする。アルファベット順で $X_j < Y_j$ ならば $X < Y$ 、 $X_j > Y_j$ ならば $X > Y$ と決定する。
- $X_i \neq Y_i$ なる $i$ が存在しないならば、$X, Y$ の長さ $|X|, \ |Y|$ を比較し、 $|X| < |Y|$ ならば $X < Y$ 、 $|X| > |Y|$ ならば $X > Y$ と決定する。
制約
- $1 \leq T \leq 10^4$
- $1 \leq N \leq 2 \times 10^5$
- $T$ と $N$ は整数
- $S$ は
A,Bからなる長さ $N$ の文字列 - $1$ つの入力ファイルにおいて、 $N$ の総和は $2 \times 10^5$ 以下
入力
入力は標準入力から与えられる。 $1$ 行目は以下の形式で与えられる。
$T$
以下、 $T$ 個のテストケースがそれぞれ以下の形式で与えられる。
$N$ $S$
出力
$T$ 行にわたって出力せよ。$i$ $(1 \leq i \leq T)$ 行目には、 $i$ 番目のテストケースに対する答えを出力せよ。
最後に改行すること。
サンプル
サンプル1
入力
5 5 ABABB 3 BAB 6 AAABBB 4 ABAB 8 BBABBABA
出力
B BAB AB ABAB BBBABA
$5$ つのテストケースが与えられています。
$1$ つめのテストケースについて、 ABABBの $1$ 文字目と $2$ 文字目は AB となっています。これを消去すると、できる文字列は ABB です。 その後、 ABB から AB を消去することで、 B を得ることができます。$S$ から操作を行うことで B より辞書順で大きい文字列を作ることはできないので答えは B です。
$2$ つめのテストケースについて、 BAB の $2, 3$ 文字目は AB となっていて、これを消去すると B が得られます。しかし、辞書順で BAB $>$ B なので、より大きい BAB が答えです。
$3$ つめのテストケースでは、 AAABBB $\rightarrow$ AABB $\rightarrow$ AB と操作することで、辞書順最大の文字列 AB を得ることができます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。