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。