No.1894 Delete AB

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 :

Shirotsume / テスター :

Kanten4205 👑

ygussany

4 ProblemId : 7812 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-07-20 02:07:34

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。