tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

JAG夏合宿に行ってきました

ICPC

とりあえず自分が書いたソースコードを張ります。

Day2 Practice (KMFContest)

F: segtree的な

#include<bits/stdc++.h>
using namespace std;
int b[100000];
int segtree[2200000];
 
	int INF=999999999;
void add(int a,int b){
	a+=(1<<20);
	while(a){
		segtree[a]=min(segtree[a],b);
		a/=2;
	}
}
int query(int a){
	int left=0;
	int right=(1<<20);
	int u=1;
	int K=19;
	while(left+1<right){
		int M=(left+right)/2;
		if(a&(1<<K)){
			if(segtree[u*2]<INF){
				u=u*2;
				right=M;
			}else{
				u=u*2+1;
				left=M;
			}
		}else{
			if(segtree[u*2+1]<INF){
				u=u*2+1;
				left=M;
			}else{
				u=u*2;
				right=M;
			}
		}
		K--;
	}
	return left;
}
int main(){
	int a;
	for(int i=0;i<2200000;i++)segtree[i]=INF;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	int ret=-1;
	int left=0;
	int right=0;
	int now=0;
	add(0,0);
	for(int i=0;i<a;i++){
		now^=b[i];
		int V=query(now);
		if(ret<(now^V)){
			ret=(now^V);
			left=segtree[(1<<20)+V];
			right=i+1;
		}else if(ret==(now^V)&&left>segtree[(1<<20)+V]){
			left=segtree[(1<<20)+V];
			right=i+1;
		}
		add(now,i+1);
	}
	printf("%d %d %d\n",ret,left+1,right);
}

A: 蟻本写しただけ

Day2 contest
1問しか解けなくてクズでした。

A:imos法やるだけ。オンサイトではFA。

#include<stdio.h>
#include<algorithm>
using namespace std;
int x[100000];
int y[100000];
int w[100000];
int A[100001];
int B[100001];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",x+i,y+i,w+i);
	}
	for(int i=0;i<a;i++){
		int L=max(0,x[i]-w[i]);
		int R=min(b,x[i]+w[i]);
		A[L]++;
		A[R]--;
	}
	for(int i=0;i<a;i++){
		int L=max(0,y[i]-w[i]);
		int R=min(c,y[i]+w[i]);
		B[L]++;
		B[R]--;
	}
	bool ok1=true;
	long long d=0LL;
	for(int i=0;i<b;i++){
		d+=A[i];
		if(!d)ok1=false;
	}
	d=0LL;
	bool ok2=true;
	for(int i=0;i<c;i++){
		d+=B[i];
		if(!d)ok2=false;
	}
	if(ok1||ok2)printf("Yes\n");
	else printf("No\n");
}

Day3 contest

D:クソ簡単なのに1WA

#include<stdio.h>
int main(){
	int a;scanf("%d",&a);
	if(a==1)printf("2\n");
	else if(a<3) printf("1\n");
	else printf("0\n");
}

B:やるだけ

#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int bfs1[100000];
int bfs2[100000];
int v1[100000];
int v2[100000];
int A[100000];
int B[100000];
vector<int> g[100000];
int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	c--;d--;
	for(int i=0;i<b;i++){
		int e,f;
		scanf("%d%d",&e,&f);
		e--;f--;
		g[e].push_back(f);
		g[f].push_back(e);
	}
	queue<int> Q;
	Q.push(c);
	for(int i=0;i<a;i++)bfs1[i]=bfs2[i]=-1;
	bfs1[c]=0;
	while(Q.size()){
		int at=Q.front();
		Q.pop();
		for(int i=0;i<g[at].size();i++){
			if(!~bfs1[g[at][i]]){
				bfs1[g[at][i]]=bfs1[at]+1;
				Q.push(g[at][i]);
			}
		}
	}
	queue<int> P;
	P.push(d);
	bfs2[d]=0;
	while(P.size()){
		int at=P.front();
		P.pop();
		for(int i=0;i<g[at].size();i++){
			if(!~bfs2[g[at][i]]){
				bfs2[g[at][i]]=bfs2[at]+1;
				P.push(g[at][i]);
			}
		}
	}
	for(int i=0;i<a;i++){
		if(~bfs1[i]){
			A[bfs1[i]]++;
		}
		if(~bfs2[i]){
			B[bfs2[i]]++;
		}
	}
	int dis=bfs1[d];
	long long ret=0LL;
	for(int i=0;i<dis-1;i++){
//		printf("%d %d\n",A[i],B[i]);
		ret+=(long long)A[i]*B[dis-2-i];
	}
	printf("%lld\n",ret);
}

C:円が出てくるが幾何ではないので良い。こういう範囲にいくつ答えがあるか系の問題は左の端を決めるとよいです。

#include<bits/stdc++.h>
using namespace std;
double EPS=1e-9;
int a,b,c,d,e,f,g,h;
int calc(int n){
	int ret=n/(2*b)*2;
	n%=(2*b);
	if(n>=h)ret++;
	if(n>=2*b-h)ret++;
	return ret;
}
int main(){
	scanf("%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h);
	c*=d;
	long long ret=0LL;
	int now=g-e;
	int at=0;
	while(now<=c){
		int x=(int)(sqrt((double)c*c-(double)now*now+EPS)+EPS);
		int r=f+x;
		int l=f-x;
		r+=500000000/b*b*2;
		l+=500000000/b*b*2;
		ret+=calc(r)-calc(l-1);
		if(at%2==0){
			now+=(a-g)*2;
		}else{
			now+=g*2;
		}
		at++;
	}
	now=-e-g;
	at=0;
	while(now>=-c){
		int x=(int)(sqrt((double)c*c-(double)now*now+EPS)+EPS);
		int r=f+x;
		int l=f-x;	
		r+=500000000/b*b*2;
		l+=500000000/b*b*2;
		ret+=calc(r)-calc(l-1);
		if(at%2==0){
			now-=(a-g)*2;
		}else{
			now-=g*2;
		}
		at++;
	}
	printf("%lld\n",ret);
}

Day4 contest
難しい。
H:直線しかないのでまだ常識的な幾何。

#include<bits/stdc++.h>
using namespace std;
double EPS=1e-9;
struct L{
	double a,b,c;
	L(double A,double B,double C){
		a=A;
		b=B;
		c=C;
	}
	L(){}
};
struct P{
	double x,y;
	P(double X,double Y){
		x=X;
		y=Y;
	}
	P(){}
};
inline bool operator < (const P &a,const P &b){
	if(a.x!=b.x){
		return a.x<b.x;
	}else return a.y<b.y;
}
P inter(L s,L t){
	double det=s.a*t.b-s.b*t.a;
	if(abs(det)<EPS){
		return P(1000000009,1000000009);
	}
	return P((t.b*s.c-s.b*t.c)/det,(t.c*s.a-s.c*t.a)/det);
}
bool eq(P a, P b){
	return abs(a.x-b.x)<EPS&&abs(a.y-b.y)<EPS;
}
double dot(P a,P b){
	return a.x*b.x+a.y*b.y;
}
double cross(P a,P b){
	return a.x*b.y-a.y*b.x;
}
double norm(P a){
	return a.x*a.x+a.y*a.y;
}
int ccw(P a,P b,P c){
	b.x-=a.x;
	b.y-=a.y;
	c.x-=a.x;
	c.y-=a.y;
	if(cross(b,c)>0)return 1;
	if(cross(b,c)<0)return -1;
	if(dot(b,c)<0)return 2;
	if(norm(b)<norm(c))return -2;
	return 0;
}
vector<P> convex_hull(vector<P> ps){
	int n=ps.size();
	int k=0;
	std::sort(ps.begin(),ps.end());
	
	vector<P> ch(2*n);
	for(int i=0;i<n;ch[k++]=ps[i++]){
		while(k>=2&&ccw(ch[k-2],ch[k-1],ps[i])<=0)--k;
	}
	
	for(int i=n-2,t=k+1;i>=0;ch[k++]=ps[i--]){
		while(k>=t&&ccw(ch[k-2],ch[k-1],ps[i])<=0)--k;
	}
	ch.resize(k-1);
	return ch;
}
 
char str[51][51];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	double mA1,mA2,mB1,mB2,mX;
	scanf("%lf%lf%lf%lf%lf",&mA1,&mA2,&mB1,&mB2,&mX);
	for(int i=0;i<a;i++){
		scanf("%s",str[i]);
	}
	double tx=0,ux=0,ty=0,uy=0;
	double vx=0,vy=0;
	double wa=0,wb=0,wc=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(str[i][j]=='A'){
				wa+=1;
				tx+=0.5+i;
				ty+=0.5+j;
			}else if(str[i][j]=='B'){
				wb+=1;
				ux+=0.5+i;
				uy+=0.5+j;
			}else if(str[i][j]=='X'){
				wc+=1;
				vx+=0.5+i;
				vy+=0.5+j;
			}
		}
	}
	wc*=mX;
	vx*=mX;
	vy*=mX;
	double ret=0;
	double div=(mA2-mA1)*(mB2-mB1);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(str[i][j]=='.')continue;
			double xl=i;
			double xh=i+1;
			double yl=j;
			double yh=j+1;
			vector<L> lines;
			lines.push_back(L(1,0,mA1));
			lines.push_back(L(1,0,mA2));
			lines.push_back(L(0,1,mB1));
			lines.push_back(L(0,1,mB2));
			lines.push_back(L(tx-wa*xl,ux-wb*xl,-vx+wc*xl));
			lines.push_back(L(tx-wa*xh,ux-wb*xh,-vx+wc*xh));
			lines.push_back(L(ty-wa*yl,uy-wb*yl,-vy+wc*yl));
			lines.push_back(L(ty-wa*yh,uy-wb*yh,-vy+wc*yh));
		//	if(i+j==0)for(int k=0;k<8;k++)printf("%f %f %f\n",lines[k].a,lines[k].b,lines[k].c);
			vector<P> cons;
			for(int k=0;k<8;k++){
				for(int l=k+1;l<8;l++){
					P v=inter(lines[k],lines[l]);
					if(abs(v.x-1000000009)>EPS){
						cons.push_back(v);
					}
				}
			}
			vector<P> ser;
			for(int k=0;k<cons.size();k++){
				bool ok=true;
				for(int l=0;l<8;l++){
					if(l%2==0){
						if(cons[k].x*lines[l].a+cons[k].y*lines[l].b+EPS<lines[l].c)ok=false;
					}else{
						if(cons[k].x*lines[l].a+cons[k].y*lines[l].b>EPS+lines[l].c)ok=false;
					}
				}
				if(ok)ser.push_back(cons[k]);
			}
			if(ser.size()>=3){
				vector<P> D=convex_hull(ser);
		//		if(i==2&&j==0)for(int k=0;k<D.size();k++)printf("%f %f\n",D[k].x,D[k].y);
				double S=0;
				for(int k=0;k<D.size();k++){
					S+=cross(D[k],D[(k+1)%D.size()]);
				}
				ret+=S/2;
		//		printf("%d %d: %f\n",i,j,S/2);
			}
		}
	}
	printf("%.12f\n",ret/div);
}