問題一覧 > 通常問題

No.2283 Prohibit Three Consecutive

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 : みここみここ / テスター : 👑 箱 cureskolcureskol 👑 potato167potato167
1 ProblemId : 9168 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-04-26 18:34:15

問題文

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

$S$ に含まれるすべての ? をそれぞれ 01 に変更することで、$S$ の中に同じ文字が三連続で現れないようにすることができるか判定してください。ただし $S$ の末尾と先頭は繋がっているものとします。

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

入力

$T$
test$_1$
$\vdots$
test$_T$

ただし test$_i$ は $i$ 番目のテストケースを表し、以下の形式で与えられる。

$N$
$S$
  • $T, N$ は整数
  • $S$ は 0, 1, ? からなる長さ $N$ の文字列
  • $1 \le T \le 5 \times 10^4$
  • $3 \le N \le 10^5$
  • すべてのテストケースの $N$ の総和は $2 \times 10^5$ を超えない

出力

$S$ の中に同じ文字が三連続で現れないようにできるなら Yes を、そうでなければ No を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
3
1?1
5
11?00
4
1101
出力
Yes
No
No

一つ目のテストケースについて、$2$ 文字目の ?0 に変更すると、$S$ の中に同じ文字は三連続で現れなくなります。

二つ目のテストケースについて、? はすべて 01 に変更する必要があることに注意してください。

三つ目のテストケースについて、$S$ の末尾と先頭は繋がっているので、$S$ において 1 が三つ連続しています。

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