GCJ2015 Round1A

満点で7位でした。

A:
英語を読むだけ。問題文いくらなんでも難しすぎると思う。解釈するのにかなり時間がかかった。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[1100];
int main(){
	int T;
	scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int a;scanf("%d",&a);
		for(int i=0;i<a;i++)scanf("%d",b+i);
		int ret1=0;
		int ret2=0;
		for(int i=1;i<a;i++){
			if(b[i-1]>b[i])ret1+=b[i-1]-b[i];
		}
		int m=0;
		for(int i=1;i<a;i++)m=max(m,b[i-1]-b[i]);
		for(int i=0;i<a-1;i++){
			ret2+=min(b[i],m);
		}
		printf("Case #%d: %d %d\n",t,ret1,ret2);
	}
}

B:
N人目がまだ散髪していない最後の時間を二分探索で求めて、その時間にどの席が空くかを調べる。これは割りきれるかどうかだけでよい。

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int c[1100];
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<a;i++)scanf("%d",c+i);
		long long left=0;
		long long right=10000000000000000LL;
		while(left+1<right){
			long long M=(left+right)/2;
			long long num=0;
			for(int i=0;i<a;i++){
				num+=(M+c[i]-1)/c[i];
			}
			if(num>=b)right=M;
			else left=M;
		}
		long long now=0;
		for(int i=0;i<a;i++)now+=(left+c[i]-1)/c[i];
		b-=now;
		int cnt=0;
		for(int i=0;i<a;i++){
			if(left%c[i]==0){
				cnt++;
				if(cnt==b){
					printf("Case #%d: %d\n",t,i+1);
					break;
				}
			}
		}
	}
}

C:
JOI合宿のBeltやConstellation2みたいなことをする。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
int x[3100];
int y[3100];
double EPS=1e-9;
double PI=acos(-1.0);
int ret[3100];
vector<double>th;
int main(){
	int T;
	scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int a;scanf("%d",&a);
		for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i);
		for(int i=0;i<a;i++){
			th.clear();
			for(int j=0;j<a;j++){
				if(i==j)continue;
				th.push_back(atan2(y[j]-y[i],x[j]-x[i]));
				th.push_back(atan2(y[j]-y[i],x[j]-x[i])+PI*2);
			}
			std::sort(th.begin(),th.end());
			int L=0;
			int u=0;
			for(int j=0;j<th.size();j++){
				while(L<th.size()&&th[j]-th[L]>PI+EPS){
					L++;
				}
				u=max(u,j-L+1);
			}
			ret[i]=a-u-1;
		}
		fprintf(stderr,"finish case #%d\n",t);
		printf("Case #%d:\n",t);
		for(int i=0;i<a;i++)printf("%d\n",ret[i]);
	}
}