kmjp's blog

競技プログラミング参加記です

Codeforces ECR #024: F. Level Generation

Fまでは割と順調でした。
http://codeforces.com/contest/818/problem/F

問題

頂点数Nが与えられる。
N頂点の単純無向グラフのうち、辺の半分以上が橋であるようなものの辺の最大値を求めよ。

解法

真ん中にC頂点の閉路を作り、そのうち1頂点の外側に(N-C)頂点をつなげることを考える。
こうすると、橋は(N-C)本できる。
辺の半分以上が橋であるためには、真ん中のC頂点に(N-C)辺以上あればいいのでC(C-1)/2≦(N-C)であればよい。
よってmin(C(C-1)/2,N-C)+(N-C)の最大値を求めよう。
この値はCに対し上に凸なので、三分探索で最大となるCを求めることができる。

int Q;
ll N;

ll ok(ll center,ll tot) {
	ll edge=tot-center;
	
	if(edge<center) return -1;
	return edge+min(edge,center*(center-1)/2);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>Q;
	while(Q--) {
		cin>>N;
		ll ma=0;
		
		if(N<100) {
			for(i=1;i<=N;i++) ma=max(ma,ok(i,N));
		}
		else {
			ll L=1,R=N;
			
			while(R-L>10) {
				ll M1=(L*2+R)/3;
				ll M2=(L+R*2)/3;
				ll A1=ok(M1,N);
				ll A2=ok(M2,N);
				if(A1>=A2) R=M2;
				if(A1<=A2) L=M1;
			}
			for(i=L;i<=R;i++) ma=max(ma,ok(i,N));
		}
		cout<<ma<<endl;
	}
}

まとめ

ちょっと自信なかったけど無事AC。