問題一覧 > 通常問題

No.3395 Range Flipping Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : 👑 loop0919 / テスター : AwashAmityOak nikoro256
ProblemId : 12908 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-12-01 22:39:33
コンテストの他の問題:
🦌 メリークリスマス！🦌

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

問題文

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

Alice さんと Bob さんは $S$ を使ってゲームを行います。
以下の操作を Alice さん、Bob さんの順にちょうど $\bm 1$ 回ずつ行います。

以下のどちらか一方を行う。

  • $1 \leq l \leq r \leq N$ を満たす整数の組 $(l, r)$ を一組選ぶ。
    $S$ の $l$ 文字目から $r$ 文字目までの各文字について、 A を B に、B を A に更新する。
  • 何も行わない。

Alice さんの目標は最終的な $S$ をできるだけ辞書順で小さくすること、Bob さんの目標は最終的な $S$ を辞書順で大きくすることです。

双方が最善を尽くしたとき$\color{red}^{*1}$の、最終的な $S$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

$\color{red}^{*1}$ 双方が最善を尽くすとは（クリックで開く）

A, B からなる長さ $N$ の文字列 $X$ であって、以下のすべてを満たすものがただ一つ存在することが示せます。

  • Bob さんがどのように操作を行っても、Alice さんが適切にゲームを進めることで最終的な $S$ を辞書順で $X$ 以下にすることができる。
  • Alice さんがどのように操作を行っても、Bob さんが適切にゲームを進めることで最終的な $S$ を辞書順で $X$ 以上にすることができる。

この $X$ を、双方が最善を尽くしたときにおける最終的な $S$ とします。

制約

  • $1 \leq T \leq 125000$
  • $1 \leq N \leq 250000$
  • $S$ は A, B からなる長さ $N$ の文字列
  • $T, N$ は整数
  • 一つの入力ファイルにおける $N$ の総和は $500000$ を超えない

入力

入力は以下の形式で標準入力から与えられます。ここで $t$ 番目 $(1 \leq t \leq T)$ のテストケースを $\mathrm{case}_t$ と表します。 

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

各テストケースは以下の形式で与えられます。 

$N$
$S$

出力

$T$ 行出力し、$t$ 行目 $(1 \leq t \leq T)$ には $t$ 番目のテストケースについての答えを出力してください。

サンプル

サンプル
入力
3
8
ABABBBAB
1
A
16
AAAABBBBAAAABBBB
出力
BBAAAAAB
B
BBAABBBBAAAABBBB

$1$ 番目のテストケースについて、例えば以下の手順でゲームが進みます。

  • Alice さんは $(l, r) = (4, 6)$ を選ぶ。$S$ は ABAAAAAB に更新される。
  • Bob さんは $(l, r) = (1, 1)$ を選ぶ。$S$ は BBAAAAAB に更新される。

$2$ 番目のテストケースについて、Alice さんがどのように操作を行ったとしても Bob さんは $S$ を B にすることができます。

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