PCK追加分

ついに2011本選が追加され始めたので。

0251:
要は各連結成分が直線かどうかを聞いている。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int deg[110000];
int UF[110000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;
	UF[a]+=UF[b];UF[b]=a;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)UF[i]=-1;
		for(int i=0;i<a;i++)deg[i]=0;
		for(int i=0;i<b;i++){
			int p,q;
			scanf("%d%d",&p,&q);
			p--;q--;
			UNION(p,q);
			deg[p]++;
			deg[q]++;
		}
		bool ok=true;
		for(int i=0;i<a;i++)if(deg[i]>2)ok=false;
		
		int rk=0;
		for(int i=0;i<a;i++)if(UF[i]<0)rk++;
		if(rk!=a-b)ok=false;
		if(ok)printf("yes\n");
		else printf("no\n");
	}
}

0253:
凸カットを持っていると本当に一瞬。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e+10;
const double PI = acos(-1);
//
Pt p[110];
Pt res[210];
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a){
		double S=(double)c/b;
		for(int i=0;i<a;i++){
			double X,Y;
			scanf("%lf%lf",&X,&Y);
			p[i]=Pt(X,Y);
		}
		double ret=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i!=j)p[j]=p[j]-p[i];
			}
			p[i]=Pt(0,0);
			double th=p[(i+1)%a].arg();
			for(int j=0;j<a;j++){
				p[j]=p[j]*Pt(cos(-th),sin(-th));
			}
			double L=0;
			double R=0;
			for(int j=0;j<a;j++)R=max(R,p[j].y);
			for(int j=0;j<100;j++){
				double M=(L+R)/2;
				int m=convexCut(a,p,Pt(1000,M),Pt(-1000,M),res);
				double tmp=0;
				for(int k=0;k<m;k++)tmp+=res[k].det(res[(k+1)%m]);
				if(tmp<0)tmp=-tmp;
				tmp/=2;
			//	printf("%f: %f\n",M,tmp);
				if(tmp>S)R=M;
				else L=M;
			}
	//		printf("%d: %f\n",i,L);
			ret=max(ret,L);
		}
		printf("%.12f\n",ret);
	}
}

0254:
要は(ある連続する区間の和)%mの最大化。だいぶ記憶が薄れてきていてlog系の良問であったことしか覚えてなかった。

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
long long c[31000];
int d[31000];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)scanf("%lld",c+i);
		long long now=0;
		for(int i=0;i<a;i++){
			now+=c[i];
			d[i]=now%b;
		}
		set<int> S;
		S.insert(b);
		int ret=0;
		for(int i=0;i<a;i++){
			int v=*(S.upper_bound(d[i]));
			ret=max(ret,(b+d[i]-v)%b);
			S.insert(d[i]);
		}
		printf("%d\n",ret);
	}
}