Codeforces #1008 : Div1 D. Maximum Polygon

なるほど。
https://codeforces.com/contest/2077/problem/D

問題

整数列Aが与えられる。
この部分列のうち、それらの辺の長さを持つ多角形が存在すること、すなわち最大値の倍が、数列の全体の総和以上にならないもので、辞書順最大のものを求めよ。

解法

解の候補のうち、部分列中の最大値は、Aの最大値上位2*log(max(A))個程度の中にある。
よってそれら最大値を総当たりしよう。
最大値が決まれば、部分列の総和がいくら以上でないといけないかわかるので、その条件を外さない範囲でAから小さい値を取り除いていけばよい。

int T;
ll N,A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	int out=0;
	FOR(j,T) {
		cin>>N;
		vector<ll> cand;
		FOR(i,N) {
			cin>>A[i];
			cand.push_back(A[i]);
		}
		sort(ALL(cand));
		reverse(ALL(cand));
		if(N>=61) cand.resize(61);
		vector<int> ret;
		FORR(c,cand) {
			
			ll S=0;
			ll ma=2*c+1;
			FOR(i,N) if(A[i]<=c) S+=A[i];
			ll cur=0;
			vector<int> st;
			FOR(i,N) if(A[i]<=c) {
				S-=A[i];
				while(st.size()&&st.back()<A[i]&&cur-st.back()+A[i]+S>=ma) {
					cur-=st.back();
					st.pop_back();
				}
				if(cur+A[i]+S>=ma) {
					st.push_back(A[i]);
					cur+=A[i];
				}
			}
			
			ret=max(ret,st);
		}
		if(ret.size()<3) {
			cout<<-1<<endl;
		}
		else {
			cout<<ret.size()<<endl;
			FORR(r,ret) cout<<r<<" ";
			cout<<endl;
		}
		
	}
	
}

まとめ

考察の初手が難しい。