問題一覧 > 通常問題

No.3395 Range Flipping Game

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 92
作問者 : 👑 loop0919 / テスター : AwashAmityOak nikoro256
お気に入りにしたユーザー ProblemId : 12908 / 自分の提出
問題文最終更新日: 2026-11-04 00:50:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:
🦌 Merry Christmas!🦌

🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄

Problem Statement

You are given a string $S$ of length $N$ consisting of A and B.

Alice and Bob play a game using $S$.
Alice and then Bob, in this order, each perform the following operation exactly $\bm 1$ time.

Do one of the following.

  • Choose a pair of integers $(l, r)$ satisfying $1 \leq l \leq r \leq N$.
    For each character from the $l$-th through the $r$-th character of $S$, change A to B and B to A.
  • Do nothing.

Alice's goal is to make the final $S$ as lexicographically small as possible, and Bob's goal is to make the final $S$ lexicographically large.

Find the final $S$ when both players play optimally$\color{red}^{*1}$.

You are given $T$ test cases; answer each of them.

$\color{red}^{*1}$ What it means for both players to play optimally (click to open)

It can be shown that there exists exactly one string $X$ of length $N$ consisting of A and B that satisfies all of the following.

  • No matter how Bob performs his operation, Alice can make the final $S$ lexicographically less than or equal to $X$ by playing the game appropriately.
  • No matter how Alice performs her operation, Bob can make the final $S$ lexicographically greater than or equal to $X$ by playing the game appropriately.

This $X$ is defined to be the final $S$ when both players play optimally.

Constraints

  • $1 \leq T \leq 125000$
  • $1 \leq N \leq 250000$
  • $S$ is a string of length $N$ consisting of A and B
  • $T, N$ are integers
  • The sum of $N$ in a single input file does not exceed $500000$

Input

The input is given from standard input in the following format, where the $t$-th test case $(1 \leq t \leq T)$ is denoted by $\mathrm{case}_t$. 

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format. 

$N$
$S$

Output

Print $T$ lines. The $t$-th line $(1 \leq t \leq T)$ should contain the answer for the $t$-th test case.

Sample

Sample
Input
3
8
ABABBBAB
1
A
16
AAAABBBBAAAABBBB
Output
BBAAAAAB
B
BBAABBBBAAAABBBB

For the $1$-st test case, the game may proceed as follows, for example.

  • Alice chooses $(l, r) = (4, 6)$. $S$ is updated to ABAAAAAB.
  • Bob chooses $(l, r) = (1, 1)$. $S$ is updated to BBAAAAAB.

For the $2$-nd test case, no matter how Alice performs her operation, Bob can make $S$ into B.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。