結果
| 問題 |
No.2283 Prohibit Three Consecutive
|
| コンテスト | |
| ユーザー |
 HIcoder
|
| 提出日時 | 2023-07-07 09:53:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,780 bytes |
| コンパイル時間 | 4,934 ms |
| コンパイル使用メモリ | 116,752 KB |
| 最終ジャッジ日時 | 2025-02-15 06:33:50 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 11 |
ソースコード
#include<iostream>
#include<set>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<numeric>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const ll INF=1LL<<60;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const ll MOD=998244353;
const double PI=acos(-1);
//bool dp[100000+5][1<<3][1<<3];
bool solve(int N,string str){
vector dp(N+1,vector<vector<bool>>(1<<3,vector<bool>(1<<3,false)));
//初期化
vector<int> prefix={0};
for(int i=0;i<3;i++){
vector<int> nx;
for(int c:prefix){
if(str[i]=='?'){
nx.push_back(2*c+1);
nx.push_back(2*c+0);
}else if(str[i]=='1'){
nx.push_back(2*c+1);
}else if(str[i]=='0'){
nx.push_back(2*c+0);
}
}
prefix=nx;
}
set<int> prefixst(prefix.begin(),prefix.end());
for(int c:prefixst){
//printf("c=%d\n",c);
for(int S=0;S<(1<<3);S++){
dp[2][c][S]=true;
}
}
for(int S=0;S<(1<<3);S++){
dp[2][S][0]=false;
dp[2][S][(1<<3)-1]=false;
dp[2][0][S]=false;
dp[2][(1<<3)-1][S]=false;
}
for(int S1=0;S1<(1<<3);S1++){
for(int S2=0;S2<(1<<3);S2++){
if( ((S1>>2)&1)==0b1 && (S2&0b11)==0b11 ){
//S1の上一桁が1, S2の下2桁が0b11
dp[2][S1][S2]=false;
}
if( ((S1>>1)&0b11)==0b11 && (S2&1)==0b1 ){
//S1の上2桁が0b11, S2の下1桁が1
dp[2][S1][S2]=false;
}
if( ((S1>>2)&1)==0b0 && (S2&0b11)==0b00 ){
//S1の上一桁が0, S2の下2桁が0b00
dp[2][S1][S2]=false;
}
if( ((S1>>1)&0b11)==0b00 && (S2&1)==0b0 ){
//S1の上2桁が0b00, S2の下1桁が0
dp[2][S1][S2]=false;
}
/*
if( ((S1>>2)&1)==1 && ((S2>>1)&3)==3 ){
//S1の下一桁が1, S2の下2桁が11
dp[2][S1][S2]=false;
}
if( ((S2>>2)&1)==1 && ((S1>>1)&3)==3 ){
//S2の下1桁が1, S1の下2桁が11
dp[2][S1][S2]=false;
}
if( ((S1&1)==0) && ((S2>>1)&3)==0 ){
dp[2][S1][S2]=false;
}
if( ((S2>>1)&1)==0 && ((S1>>2)&1)==0 ){
dp[2][S1][S2]=false;
}
*/
}
}
for(int i=2;i<N;i++){
for(int S2=0;S2<(1<<3);S2++){
for(int S1=0;S1<(1<<3);S1++){
if(!dp[i][S1][S2]) continue;
//int tmp=(S1<<1)&((1<<3)-1);
int tmp=((S1>>1)<<1);
if(str[i]=='1'){
int to=tmp|0b001;
if(to!=0b111 && to!=0){
dp[i+1][to][S2]=true;
}
}
else if(str[i]=='0'){
int to=tmp|0b000;
if(to!=0b111 && to!=0){
dp[i+1][to][S2]=true;
}
}else{
int to1=tmp|0b001;
int to0=tmp|0b000;
if(to1!=0b111 && to1!=0){
dp[i+1][to1][S2]=true;
}
if(to0!=0b111 && to0!=0){
dp[i+1][to0][S2]=true;
}
}
}
}
}
vector<int> suffix={0};
for(int i=N-3;i<N;i++){
vector<int> nx;
for(int c:suffix){
if(str[i]=='?'){
nx.push_back(2*c+1);
nx.push_back(2*c+0);
}else if(str[i]=='1'){
nx.push_back(2*c+1);
}else if(str[i]=='0'){
nx.push_back(2*c+0);
}
}
suffix=nx;
}
set<int> suffixst(suffix.begin(),suffix.end());
bool res=false;
for(int S=0;S<(1<<3);S++){
if(dp[N][S][S] && suffixst.count(S)){
if(S==0b000 || S==0b111 ) continue;
//cout<<"S="<<S<<endl;
/*
if( ((S>>2)&1)==1 && ((S>>1)&3)==3 ){
//Sの下一桁が1, Sの下2桁が11
continue;
}
if( ((S>>1)&1)==3 && ((S>>2)&1)==1 ){
continue;
}
if( ((S>>2)&1)==0 && ((S>>1)&3)==0 ){
//Sの下一桁が1, Sの下2桁が11
continue;
}
if( ((S>>1)&1)==0 && ((S>>2)&1)==0 ){
continue;
}
*/
res=true;
}
}
auto printb=[](int n){
string res="";
if(n==0){
//res+="0";
res+='0';
return res;
}
while(n>0){
if(n&1){
//res+="1";
res+='1';
}else{
//res+="0";
res+='0';
}
n/=2;
}
reverse(res.begin(),res.end());
return res;
};
/*
for(int i=2;i<=N;i++){
for(int S2=0;S2<(1<<3);S2++){
for(int S1=0;S1<(1<<3);S1++){
cout<<"dp["<<i<<"]["<<printb(S1)<<"]["<<printb(S2)<<"]="<<(dp[i][S1][S2]?1:0)<<",";
}
cout<<endl;
}
}
*/
return res;
}
int main(){
int T;
cin>>T;
for(int t=0;t<T;t++){
int N;
cin>>N;
string S;
cin>>S;
bool flag=solve(N,S);
cout<<(flag?"Yes":"No")<<endl;
/*
vector dp(N+1,vector<vector<bool>>(2,vector<bool>(2,false)));
for(int t1=0;t1<2;t1++){
for(int t2=0;t2<2;t2++){
dp[0][t1][t2]=true;
}
}
for(int i=0;i<N;i++){
if(S[i]=='1'){
//dp[i+1][1][1]=false;
for(int t1=0;t1<2;t1++){
for(int t2=0;t2<2;t2++){
if(dp[i][t1][t2]){
if(t1!=t2){
dp[i+1][1][t1]=true;
dp[i+1][1][t1]=true;
}else{
//t1==t2
if(t1!=1){
dp[i+1][1][t1]=true;
}
}
}
}
}
}
else if(S[i]=='0'){
for(int t1=0;t1<2;t1++){
for(int t2=0;t2<2;t2++){
if(dp[i][t1][t2]){
if(t1!=t2){
dp[i+1][0][t1]=true;
dp[i+1][0][t1]=true;
}else{
//t1==t2
if(t1!=0){
dp[i+1][0][t1]=true;
}
}
}
}
}
}else{
//S[i]=='?'
for(int t1=0;t1<2;t1++){
for(int t2=0;t2<2;t2++){
if(dp[i][t1][t2]){
if(t1!=t2){
dp[i+1][1][t1]=true;
dp[i+1][0][t1]=true;
}else{
//t1==t2
//t1(=t2)とは異なるほう
dp[i+1][1-t1][t1]=true;
}
}
}
}
}
}
*/
}//テストケースtの終了
}