kmjp's blog

競技プログラミング参加記です

Codeforces #686 : Div3. F. Array Partition

なんか順調で1位が取れた回。
https://codeforces.com/contest/1454/problem/F

問題

整数列Aが与えられる。
Aを空でない連続部分列B+C+Dに分割したとき、max(B)=min(C)=max(D)となるようにできるか。

解法

max(B)=min(C)=max(D)=mとしてmを総当たりする。

m未満の値の添え字の集合Lと、mを超えた値の添え字の集合Rを考える。
Aのうちm未満の値はBまたはD、mより大きな値はCに入るようにできるかL,Rを使って判定すればよい。

int T;
int N;
ll A[202020];
set<int> L,R;
map<int,set<int>> M;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		L.clear();
		R.clear();
		M.clear();
		L.insert(-1);
		L.insert(N+1);
		FOR(i,N) {
			cin>>A[i];
			M[-A[i]].insert(i);
			L.insert(i);
		}
		vector<int> ret;
		FORR(m,M) {
			x=m.first;
			auto v=m.second;
			FORR(c,v) L.erase(c);
			
			if(v.size()>=3) {
				if(R.empty()) {
					x=*next(v.begin());
					ret={x,1,N-(x+1)};
				}
				else {
					int a=-1,b=-1;
					if(R.size()==1) {
						a=b=*R.begin();
					}
					else if(R.size()>=2) {
						a=*R.begin();
						b=*R.rbegin();
						
						if(*L.lower_bound(a)<b) {
							a=N+1;
						}
					}
				
					if(a<=N) {
						int lR=min(*v.rbegin(),*L.lower_bound(b));
						int lL=max(*v.begin(),*prev(L.lower_bound(a)));
						int lM=*v.lower_bound(lL+1);
						if(lM<lR&&lR>*R.rbegin()&&lL<*R.begin()) {
							//cout<<x<<" "<<a<<" "<<b<<" "<<lL<<" "<<lM<<" "<<lR<<endl;
							ret={lL+1,lR-(lL+1),N-lR};
						}
					}
				}
			}
			
			FORR(c,v) R.insert(c);
		}
		
		
		if(ret.size()) {
			cout<<"YES"<<endl;
			cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
	}
}

まとめ

結構時間かかったけどなんかいい順位だった。前半が良かったのかな。