読者です 読者をやめる 読者になる 読者になる

Facebook Hacker Cup 2015 Round 3

いやあもうホント嬉しい。

10: Boomerang
最初に投げる先の頂点を選んで、行った先からのatan2でソートしてO(N^2 log N)。
1点しか行き先がなくて1*1みたいなので落としやすいので気をつけましょう。

#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);
// ライブラリ省略
double th[3100];
Pt p[3100];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		double X,Y;
		scanf("%lf%lf",&X,&Y);
		Pt p0=Pt(X,Y);
		int b,a;
		scanf("%d%d",&b,&a);
		for(int i=0;i<a;i++){
			double ix,iy;
			scanf("%lf%lf",&ix,&iy);
			p[i]=Pt(ix,iy);
		}
		p0=p0*Pt(cos(1.0),sin(1.0));
		for(int i=0;i<a;i++)p[i]=p[i]*Pt(cos(1.0),sin(1.0));
		int ret=0;
		for(int i=0;i<a;i++){
			if((p[i]-p0).ABS()>EPS+b)continue;
			Pt at=p0+(p[i]-p0)/(p[i]-p0).ABS()*(double)b;
			int A=0;
			for(int j=0;j<a;j++){
				if((p[j]-p0).ABS()<EPS||(p[j]-at).ABS()<EPS)A++;
				else if(iSP(p0,p[j],at)==2){
					A++;
				}
			}
			int C=0;
			int B=0;
			int sz=0;
			for(int j=0;j<a;j++){
				if((at-p[j]).ABS()<EPS){
					C++;continue;
				}
				th[sz++]=atan2(p[j].y-at.y,p[j].x-at.x);
			}
			std::sort(th,th+sz);
			int now=0;
			B=C;
			for(int j=0;j<sz;j++){
				if(j==0||th[j]-th[j-1]<EPS)now++;
				else now=1;
				B=max(B,C+now);
			}
			ret=max(ret,A*B);
		//	printf("%f %f %f %f %d %d\n",at.x,at.y,p[0].x,p[0].y,A,B);
		}
		printf("Case #%d: %d\n",t,ret);
	}
}

15: Lunch Scheduling
まあどうせ座標圧縮してからdp[i][j]:時間iまでは大丈夫でそのうちWさんがj回働いたときのJさんが働く回数の最小値、みたいなDPなんだろうなあと思ったけどなかなかオーダー削るのが面白い。
i!=jでA[i]<=A[j]

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[12100][3100];
int z[12100];
int A[3100];
int B[3100];
int C[3100];
int D[3100];
int pv[3100];
int qv[3100];
pair<int,int>p[3100];
pair<int,int>q[3100];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		int sz=0;
		for(int i=0;i<a;i++)pv[i]=0;
		for(int i=0;i<b;i++)qv[i]=0;
		z[sz++]=0;
		z[sz++]=80000000;
		for(int i=0;i<a;i++){
			scanf("%d%d",A+i,B+i);
			z[sz++]=A[i];
			z[sz++]=B[i];
		}
		for(int i=0;i<b;i++){
			scanf("%d%d",C+i,D+i);
			z[sz++]=C[i];
			z[sz++]=D[i];
		}
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i==j)continue;
				if(A[j]<=A[i]&&B[i]<=B[j])pv[i]=1;
			}
		}
		for(int i=0;i<b;i++){
			for(int j=0;j<b;j++){
				if(i==j)continue;
				if(C[j]<=C[i]&&D[i]<=D[j])qv[i]=1;
			}
		}
		std::sort(z,z+sz);
		int ps=0;
		int qs=0;
		for(int i=0;i<a;i++){
			if(pv[i])continue;
			p[ps++]=make_pair(A[i],B[i]);
		}
		for(int i=0;i<b;i++){
			if(qv[i])continue;
			q[qs++]=make_pair(C[i],D[i]);
		}
		std::sort(p,p+ps);
		std::sort(q,q+qs);
		for(int i=0;i<sz+10;i++){
			for(int j=0;j<a+10;j++){
				dp[i][j]=999999999;
			}
		}
		dp[0][0]=0;
		for(int i=0;i<sz;i++){
			for(int j=0;j<=a;j++){
				if(dp[i][j]>9999999)continue;
			//	printf("%d %d: %d\n",z[i],j,dp[i][j]);
				int at=lower_bound(p,p+ps,make_pair(z[i]+c,0))-p-1;
				if(at>=0&&z[i]<p[at].second){
					int to=lower_bound(z,z+sz,p[at].second)-z;
					dp[to][j+1]=min(dp[to][j+1],dp[i][j]);
				}
				at=lower_bound(p,p+ps,make_pair(z[i],0))-p-1;
				if(at>=0&&z[i]<p[at].second){
					int to=lower_bound(z,z+sz,p[at].second)-z;
					dp[to][j+1]=min(dp[to][j+1],dp[i][j]);
				}
				at=lower_bound(q,q+qs,make_pair(z[i]+c,0))-q-1;
				if(at>=0&&z[i]<q[at].second){
					int to=lower_bound(z,z+sz,q[at].second)-z;
					dp[to][j]=min(dp[to][j],dp[i][j]+1);
				}
				at=lower_bound(q,q+ps,make_pair(z[i],0))-q-1;
				if(at>=0&&z[i]<q[at].second){
					int to=lower_bound(z,z+sz,q[at].second)-z;
					dp[to][j]=min(dp[to][j],dp[i][j]+1);
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<sz;i++)
			for(int j=0;j<=a;j++){
				if(80000000-z[i]<c)ret=min(ret,max(j,dp[i][j]));
			}
		if(ret>9999999)printf("Case #%d: Lunchtime\n",t);
		else printf("Case #%d: %d\n",t,ret);
	}
}

35: Gentrification
f:id:tozangezan:20150201100259p:plain
(図は入力例5に対応)
こんなグラフ作って流したら通ったんだけどなぜなんですか。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
const int D_MAX_V=1100;
const int D_v_size=1100;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1));
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}

int G[510][510];
int UF[510];
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 sz[510];
vector<int>g[510];
int num[510];
int main(){
	int T;scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int a,b;scanf("%d%d",&a,&b);
		for(int i=0;i<510;i++)g[i].clear();
		for(int i=0;i<a;i++)UF[i]=-1;
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)
			G[i][j]=0;
		for(int i=0;i<a;i++)G[i][i]=0;
		for(int i=0;i<b;i++){
			int p,q;
			scanf("%d%d",&p,&q);
			G[p][q]=1;
		}
		for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++)
			G[i][j]|=(G[i][k]&G[k][j]);
		for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
			if(G[i][j]&&G[j][i])UNION(i,j);
		}
		int ind=0;
		for(int i=0;i<a;i++){
			if(UF[i]<0){
				num[i]=ind;
				sz[ind++]=-UF[i];
			}
		}
		for(int i=0;i<a;i++){
			if(UF[i]>=0)num[i]=num[FIND(i)];
		}
		for(int i=0;i<a;i++)for(int j=0;j<a;j++){
			if(UF[i]<0&&UF[j]<0&&i!=j){
				if(G[i][j])g[num[i]].push_back(num[j]);
			}
		}
		int ss=ind*2;
		int st=ind*2+1;
		for(int i=0;i<D_MAX_V;i++){
			D_G[i].clear();
			D_level[i]=D_iter[i]=0;
		}
		for(int i=0;i<ind;i++){
			add_edge(ss,i,sz[i]);
			add_edge(i+ind,st,sz[i]);
		}
		for(int i=0;i<ind;i++){
			for(int j=0;j<g[i].size();j++)add_edge(i,ind+g[i][j],99999999);
		}
		printf("Case #%d: %d\n",t,a-max_flow(ss,st));
	}
}

40: Fox Rocks
そもそも解けないからあれなんだけど、りんごさんによると結構変なケースがあるらしく一発で通すのは結構難しいらしい。

60pts 2:58:49 (17th)
決勝進出!がんばるぞ!