提出 #62692487

---

ソースコード 拡げる

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define ar array
//~ #define int ll

template<class T, class U> bool umin(T& a, U b) { if(b < a) { a = b; return true; } return false; }
template<class T, class U> bool umax(T& a, U b) { if(a < b) { a = b; return true; } return false; }

const int mod = 1e9 + 7;
void add(int& a, const int b){
	a += b;
	while(a >= mod) a -= mod;
	while(a < 0) a += mod;
}

void solve(){
	int n; cin >> n;
	
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	
	auto find_ans = [&](vector<int> v){
		int n = v.size();
		vector<vector<int>> tp(n, vector<int>(9, false));
		vector<vector<int>> dp(n, vector<int>(9, false));
		
		if(!v[0] || !v[1]){
			tp[2][5] = dp[2][5] = true;
			if(v[0]){
				for(int t=0;t<9;t++) dp[2][t] = true;
			}
		} else {
			for(int t=0;t<9;t++){
				tp[2][t] = dp[2][t] = true;
			}
		}
		
		auto check = [&](int hash){
			return hash == 5 || hash == 21;
		};
		
		for(int i=2;i + 1<n;i++){
			for(int a=0;a<3;a++){
				for(int b=0;b<3;b++){
					for(int c=0;c<3;c++){
						//~ dp[a * 3 + b] -> dp[b * 3 + c]
						if(check(a * 9 + b * 3 + c) || (v[i] && v[i - 1])){
							tp[i + 1][b * 3 + c] |= dp[i][a * 3 + b];
						}
						
						dp[i + 1][b * 3 + c] |= tp[i][a * 3 + b];
					}
				}
			}
		}
		
		bool ans = dp[n - 1][3];
		
		if(v[n - 1]){
			for(int t=0;t<9;t++){
				ans |= tp[n - 1][t];
				if(v[n - 2]) ans |= dp[n - 1][t];
			}
		}
		
		return ans;
	};
	
	vector<int> b = a;
	b.erase(b.begin());
	b.push_back(a[0]);
	
	if(find_ans(a) || find_ans(b)){
		cout<<"Yes\n";
	} else {
		cout<<"No\n";
	}
	
	//~ if(is || n % 4 == 0) cout<<"Yes\n";
	//~ else cout<<"No\n";
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int t = 1;
	
	//~ cin >> t;
	while(t--){
		solve();
	}
}

提出情報

ジャッジ結果