結果

問題 No.3395 Range Flipping Game
コンテスト
ユーザー cleantted
提出日時 2025-12-02 23:41:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 1,410 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 122,392 KB
最終ジャッジ日時 2025-12-02 23:42:03
合計ジャッジ時間 6,797 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Bobの最善は、最初に見つかったAの塊をBにすること
# なので、 Alice の最善は、なるべく 「ABA*」をつくることになる
# Sが2文字以下のとき、どうやってもすべてBになるので、3文字以上のときを考える
# - 「AAA*」のとき、「ABA*」にする (2文字目のみ)
# - 「AAB*」のとき、「ABA*」+3文字目から連続するBをAにする
# - 「ABA*」のとき、「ABA*」+最初に見つかった連続するBをAにする
# - 「ABB*」のとき、「ABA*」+3文字目から連続するBをAにする
# - 「BAA*」のとき、「ABA*」にする (1,2文字目のみ)
# - 「BAB*」のとき、「ABA*」+3文字目から連続するBをAにする
# - 「BBA*」のとき、「ABA*」にする (1文字目のみ)
# - 「BBB*」のときだけ、どうやっても最終的に全部Bになる
# 
# うまくまとめると、
# - 「AB*」or「*AB」のとき、 3文字目以降で最初に見つかったBの塊をAにする
# - 1, 2文字目をBにする
# になる

def f():
	N = int(input())
	S = list(input().strip())
	
	if N <= 2:
		print("B" * N)
		return
	
	if S[0] + S[1] == "AB" or S[1] + S[2] == "AB":
		i = 2
		while i < N and S[i] == "A":
			i += 1
		j = i + 1
		while j <= N and S[j - 1] == "B":
			S[j - 1] = "A"
			j += 1
	
	S[0] = "B"
	S[1] = "B"
	print(*S, sep="")
	
T = int(input())
for _ in range(T):
	f()
0