AOJ 0617: Ball

しばらく諸事情で競技プログラミングができないので、記事を書いておくことにする。

非典型で良問だと思う。

• 二分探索をする
• 木を作る
• より多く必要な人数を木DPする

ということを気にすればOK。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
vector<int>g[310000];
pair<int,int>z[110000];
int in[110000];
int st[110000];
int n;
int solve(int a,int b){
	if(a<n){
		if(~st[a]){
			if(st[a]>=b)return 0;
			else return 99999999;
		}
		return 1;
	}
	int um=0;
	int sum=0;
	for(int i=0;i<3;i++){
		int t=solve(g[a][i],b);
		um=max(t,um);
		sum+=t;
	}
	return min(99999999,sum-um);
}
int amari[110000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	n=a;
	for(int i=0;i<b;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		q--;
		in[i]=q;
		z[i]=make_pair(p,-i);
	}
	for(int i=b;i<a;i++){
		int p;scanf("%d",&p);
		z[i]=make_pair(p,-i);
	}
	std::sort(z,z+a);
	int as=0;
	for(int i=0;i<a;i++)st[i]=-1;
	for(int i=0;i<a;i++){
		if(-z[i].second<b){
			st[in[-z[i].second]]=i;
		}else{
			amari[as++]=i;
		}
	}
	int sz=a;
	queue<int>Q;
	for(int i=0;i<a;i++)Q.push(i);
	while(Q.size()>1){
		int t1=Q.front();Q.pop();
		int t2=Q.front();Q.pop();
		int t3=Q.front();Q.pop();
		g[sz].push_back(t1);
		g[sz].push_back(t2);
		g[sz].push_back(t3);
		Q.push(sz);
		sz++;
	}
	int left=0;
	int right=a;
	while(left+1<right){
		int M=(left+right)/2;
		int use=solve(sz-1,M);
		int can=as-(lower_bound(amari,amari+as,M)-amari);
		if(use<=can)left=M;
		else right=M;
	}
	printf("%d\n",z[left].first);
}