配点 : 500 点
問題文
d と p からなる長さ L の文字列 T に対して、T を 180 度回転した文字列を f(T) と表します。より厳密には、f(T) を次の条件を満たす文字列として定めます。
- f(T) は
d と p からなる長さ L の文字列である。
- 1≤i≤L であるすべての整数 i について、f(T) の i 文字目は T の L+1−i 文字目と異なる。
例えば T= ddddd のとき f(T)= ppppp, T= dpdppp のとき f(T)= dddpdp です。
d と p からなる長さ N の文字列 S が与えられます。
あなたは次の操作を 0 回以上 1 回以下行うことができます。
- 1≤L≤R≤N である整数の組 (L,R) を 1 つ選び、S の L 文字目から R 文字目までからなる部分文字列を T とする。そして、S の L 文字目から R 文字目までを f(T) に置き換える。
例えば S= dpdpp, (L,R)=(2,4) の場合、T= pdp, f(T)= dpd なので S は ddpdp に変化します。
最終的な S としてあり得る文字列のうち辞書順最小のものを出力してください。
辞書順とは？
文字列 S=S1S2…S∣S∣ が文字列 T=T1T2…T∣T∣ より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
ここで、∣S∣,∣T∣ はそれぞれ S,T の長さを表します。
- ∣S∣<∣T∣ かつ S1S2…S∣S∣=T1T2…T∣S∣。
- ある整数 1≤i≤min{∣S∣,∣T∣} が存在して、下記の 2 つがともに成り立つ。
- S1S2…Si−1=T1T2…Ti−1
- Si が Ti よりアルファベット順で小さい文字である。
制約
- 1≤N≤5000
- S は
d と p からなる長さ N の文字列
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
S
出力
答えを出力せよ。
6
dpdppd
dddpdd
(L,R)=(2,5) とします。T= pdpp, f(T)= ddpd なので、操作後の S は dddpdd になります。
得られる文字列のうち dddpdd が辞書順最小なので、これを出力します。
3
ddd
ddd
操作を行わないことが最適な場合もあります。
11
ddpdpdppddp
ddddpdpdddp
