Codeforces #906 : Div1 B. Doremy's Connecting Plan

不参加だった回。
https://codeforces.com/contest/1889/problem/B

問題

N点の無向グラフを考える。
各点vにはパラメータA[v]が設定されている。
また、正整数Cが指定される。

2点i,j間に辺を増やすには、辺を足した際i,jを含む連結成分に含まれる点vに対応するA[v]の総和が、i*j*C以上である必要がある。
全点を連結させることができるか。

解法

極力1番の点と辺を張るのが効率が良い。
頂点iが1番の辺と連結できるかiの小さい順に判定しよう。
今1番の点を含む連結成分のA[v]の和をSとすると、S+A[i]≧i*Cならと1番～i番の全部の点を連結にできる。

int T,N;
ll C,A[202020],S[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C;
		int cur=0;
		FOR(i,N) {
			cin>>A[i];
			S[i]=A[i];
			if(i) S[i]+=S[i-1];
			if(i&&S[cur]+A[i]>=(i+1)*C) cur=i;
		}
		if(cur==N-1) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
	}
}

まとめ

1250ptだけど、コードは短い。