Codeforces ECR #101 : F. Power Sockets

ECRのボス問にしては簡単な回。
https://codeforces.com/contest/1469/problem/F

問題

N個のチェーンがある。各チェーンは、L[i]個の頂点を直列に辺でつないだパスである。
これらのチェーンを使い、以下の根付き木を成すグラフを作る。

初期状態で、白い根頂点が1つ存在する。
ここで、白い頂点を1つ選び、未選択のチェーンの1つを選んで、白い頂点とチェーン中の１頂点を選び辺でつなぐことができる。
この時、根付き木側の白頂点は黒くなる。
全チェーンを使ってもよいし使わなくてもよい。

この時、白頂点がK個以上できるような根付き木が作れるならば、根からK番目に近い白頂点までの距離を求めよ。

解法

戦略としては、以下の通り。

• 浅い位置にある白頂点から優先的に、チェーンをつなぐ。
• 長いチェーンから先に使う。その際白頂点とつなぐ部分はチェーンの中央。

区間加算と、lower_boundが取れるBITを使い、各深さにある白頂点数を管理すれば、白頂点を選ぶのもチェーンの追加による白頂点の追加もO(logL)で行える。

int N,K;
int L[202020];

template<class V, int ME> class BIT_r {
public:
	V bit[2][1<<ME];
	BIT_r(){clear();};
	void clear() {ZERO(bit);};
	
	void update(int entry, V val0, V val1) {
		entry++;
		while(entry <= 1<<ME) bit[0][entry-1]+=val0, bit[1][entry-1] += val1, entry += entry & -entry;
	}
	V total(int entry) {
		if(entry<0) return 0;
		int e=entry++;
		V v0=0,v1=0;
		while(entry>0) v0+=bit[0][entry-1], v1+=bit[1][entry-1], entry -= entry & -entry;
		return e*v0+v1;
	}
	void add(int L, int R, V val) { // add val to L<=x<=R
		update(L,val,-val*(L-1));
		update(R+1,-val,val*R);
	}
	int lower_bound(V val) { //単調増加の時のみ使える
		V v0=0,v1=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) {
			if((ent+(1<<i)-1)*(v0+bit[0][ent+(1<<i)-1])+(v1+bit[1][ent+(1<<i)-1])<val) {
				v0+=bit[0][ent+(1<<i)-1];
				v1+=bit[1][ent+(1<<i)-1];
				ent+=(1<<i);
			}
		}
		return ent;
	}
};
BIT_r<ll,23> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	ll W=1;
	FOR(i,N) cin>>L[i];
	
	int ret=1<<30;
	
	sort(L,L+N);
	reverse(L,L+N);
	
	bt.add(0,0,1);
	FOR(i,N) {
		x=bt.lower_bound(1);
		bt.add(x,x,-1);
		if(L[i]%2==0) {
			bt.add(x+2,x+2+L[i]/2-1,1);
			bt.add(x+2,x+2+L[i]/2-2,1);
		}
		else {
			bt.add(x+2,x+2+L[i]/2-1,1);
			bt.add(x+2,x+2+L[i]/2-1,1);
		}
		if(bt.total(1<<20)>=K) {
			ret=min(ret,bt.lower_bound(K));
		}
	}
	
	if(ret==1<<30) ret=-1;
	cout<<ret<<endl;
	
}

まとめ

珍しい。