yukicoder : No.1341 真ん中を入れ替えて門松列

これは★4だけどあまり難しく感じなかったな。
https://yukicoder.me/problems/no/1341

問題

N要素の3つの数列A,B,Cが与えられる。
B内はいずれも任意に並べ替え可能であるとき、

• 3つ組(A[i],B[i],C[i])がいずれも門松列となるようにできるか
• その時、max(A[i],B[i],C[i])の総和をM以上にできるか

を判定せよ。

解法

Bが任意に並べ替え可能ということは、言い換えればA[i],C[i]の対が任意に並べ替え可能であると同義である。
まず、Bを昇順ソートしておく。
その時、Bのprefixの何要素かはB[i]がA[i]やC[i]より小さくなるようにし、残りsuffixではB[i]がA[i]やC[i]より大きい、というケースを考えよう。

Prefix何要素が「B[i]がA[i]やC[i]より小さくなる」かを総当たりし、B[i]に対して(A[i],C[i])を条件を満たすよう割り振れるか検証すればよい。
また、その時はsum(max(A[i],B[i],C[i]))の値は一意に確定するので、それがM以上かどうか確認すればよい。

int N;
ll M;
int B[3030];
pair<int,int> P[3030];
int vis[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x>>B[i]>>y;
		if(x>y) swap(x,y);
		if(x==y) return _P("NO\n");
		P[i]={y,x};
	}
	ll ma=-1;
	sort(B,B+N);
	sort(P,P+N);
	
	FOR(k,N+1) {
		ZERO(vis);
		ll ok=0;
		x=N-1;
		multiset<int> S;
		FOR(i,k) S.insert(B[i]);
		for(i=N-1;i>=0;i--) if(S.size()) {
			auto it=S.lower_bound(P[i].second);
			if(it!=S.begin()) {
				it--;
				vis[i]=1;
				ok+=P[i].first;
				S.erase(it);
			}
		}
		if(S.size()) continue;
		x=0;
		for(i=k;i<N;i++) {
			while(x<N&&vis[x]) x++;
			if(x==N||P[x].first>=B[i]) break;
			x++;
			ok+=B[i];
		}
		if(i<N) continue;
		ma=max(ma,ok);
	}
	
	if(ma==-1) {
		cout<<"NO"<<endl;
	}
	else {
		cout<<"YES"<<endl;
		if(ma<M) cout<<"NO"<<endl;
		else cout<<"KADOMATSU!"<<endl;
	}
}

まとめ

★3.5でもいいかも。