yukicoder : No.2343 (l+r)/2

これはどうにか解けた。
https://yukicoder.me/problems/no/2343

問題

初期状態が01で構成される数列Aが与えられる。
隣接する2要素を選び、その平均値で置き換えることを繰り返したとき、Aを0.5 1要素にすることができるか。

解法

先頭と末尾が異なるとき、隣接する同じ値の要素を先に平均化で消すと、10101010のようになるので、最初に2個ずつ組にして全部0.5にしてしまえばよい。
先頭と末尾が同じ時、先頭と異なる値が2連続する位置があると、0.5にできる。101010|010101のように、０が2連続したところで区切ると、1010…と0101…の列が作れるので、それぞれ0.5にできるためである。
残るは、1010101のように、両端と異なる値が、2連続している箇所が無いケースである。これも総当たりで探すと長さ9以上なら条件を満たす処理順が存在することがわかる。

int T;
int N;
int A[202020];

void dfs(vector<double> A) {
	if(A.size()==1) {
		if(A[0]<0.51) cout<<A[0]<<endl;
	}
	else {
		int i,j;
		FOR(i,A.size()-1) {
			vector<double> B;
			FOR(j,A.size()) {
				if(j==i+1) {
					B.back()=(B.back()+A[j])/2;
				}
				else {
					B.push_back(A[j]);
				}
			}
			dfs(B);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	/*
	vector<double> V={1,0,1,0,1,0,1};
	dfs(V);
	return;
	*/
	
	cin>>T;
	while(T--) {
		cin>>N;
		int C[2]={},D[2]={};
		FOR(i,N) {
			cin>>A[i];
			if(i&&A[i]==A[i-1]) C[A[i]]++;
			D[A[i]]++;
		}
		
		if(A[0]!=A[N-1]||C[A[0]^1]||D[A[0]^1]>=4) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

101010101で0.5にできるのが意外だった。