Codeforces #641 Div1 B. Orac and Medians

これ750ptかと思ったらむしろ1250ptなのか。
http://codeforces.com/contest/1349/problem/B

問題

整数列Aと整数Kが与えられる。
Aのうち部分列を選び、その値をmedianにそろえるということを任意回数行う。
A全体をKにできるか。

解法

以下に着目しよう。

• 並んだ3要素中2要素以上がK以上なら、全体をK以上にできる。
• KとK以上の値が隣接していたら、両方Kにそろえられる。

まずAにKが1つはなければならない。
あとは上の内容がどれかを満たすか愚直に見ていこう。

int T;
int N,K;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		int C[3]={};
		FOR(i,N) {
			cin>>A[i];
			if(A[i]<K) A[i]=0;
			else if(A[i]==K) A[i]=1;
			else A[i]=2;
			C[A[i]]++;
		}
		
		if(C[1]==0) {
			cout<<"no"<<endl;
			continue;
		}
		if(C[0]==0) {
			cout<<"yes"<<endl;
			continue;
		}
		
		FOR(i,N-1) {
			if(A[i]>=1&&A[i+1]>=1) {
				cout<<"yes"<<endl;
				break;
			}
		}
		if(i<N-1) continue;
		
		FOR(i,N-2) {
			if((A[i]>0)+(A[i+1]>0)+(A[i+2]>0)>=2) {
				cout<<"yes"<<endl;
				break;
			}
		}
		if(i<N-2) continue;
		
		
		
		cout<<"no"<<endl;
		
	}
}

まとめ

もっと短く書けたかな。