tozangezan's diary

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

天下一プログラマーコンテスト2016 予選A

反省点がないので文章はほぼないです。

Irrelevant:

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int ret=0;
	for(int i=1;i<=100;i++){
		if(i%3&&i%5)ret+=i;
	}
	printf("%d\n",ret);
}
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>g[1100];
int t[1100];
int ret=0;
int mm[1100];
void dfs(int a){
	int tmp=999999;
	if(a==0)tmp=0;
	if(t[a])tmp=t[a];
	else{
		
		for(int i=0;i<g[a].size();i++){
			dfs(g[a][i]);
			tmp=min(tmp,mm[g[a][i]]);
		}
		for(int i=0;i<g[a].size();i++){
			ret+=mm[g[a][i]]-tmp;
		}
	}
	mm[a]=tmp;
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a-1;i++){
		int s;scanf("%d",&s);
		g[s].push_back(i+1);
	}
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		t[p]=q;
	}
	dfs(0);
	printf("%d\n",ret);
}
#include<stdio.h>
#include<algorithm>
using namespace std;
int g[30][30];
char A[2100];
char B[2100];
char ans[30];
int g2[30][30];
bool chk(){
	for(int k=0;k<26;k++)for(int i=0;i<26;i++)for(int j=0;j<26;j++)
		g2[i][j]|=(g2[i][k]&g2[k][j]);
	for(int i=0;i<26;i++)for(int j=i+1;j<26;j++)if(g2[i][j]&&g2[j][i])return false;
	return true;
}
int used[30];
int main(){
	int a;scanf("%d",&a);
	bool dame=false;
	for(int i=0;i<26;i++)g[i][i]=1;
	for(int i=0;i<a;i++){
		scanf("%s%s",A,B);
		for(int j=0;A[j];j++){
			if(!B[j]){
				dame=true;break;
			}
			if(A[j]!=B[j]){
				g[A[j]-'a'][B[j]-'a']=1;
				break;
			}
		}
	}
	if(dame){
		printf("-1\n");return 0;
	}
	for(int i=0;i<26;i++)for(int j=0;j<26;j++)g2[i][j]=g[i][j];
	if(!chk()){
		printf("-1\n");return 0;
	}
	for(int i=0;i<26;i++){
		for(int j=0;j<26;j++){
			if(used[j])continue;
			for(int I=0;I<26;I++)for(int J=0;J<26;J++)g2[I][J]=g[I][J];
			for(int k=0;k<26;k++){
				if(!used[k]&&j!=k)g2[j][k]=1;
			}
			if(chk()){
				used[j]=true;
				ans[i]='a'+j;
			//	printf("%c\n",ans[i]);
				break;
			}
		}
	}
	printf("%s\n",ans);
}

D:
適当なことをして座圧するだけ。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
char in[2];
vector<int>g[30];
long long x[30];
long long y[30];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
long long p3[32];
void dfs(int a,int b,int c,long long X,long long Y,int d){
	x[a]=X;
	y[a]=Y;
	int t=0;
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		if(c==t)t++;
		dfs(g[a][i],a,t^2,X+p3[31-d]*dx[t],Y+p3[31-d]*dy[t],d+1);
		t++;
	}
}
long long zx[32];
long long zy[32];
int px[32];
int py[32];
char ret[120][120];
int S[30];
int T[30];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		scanf("%s",in);
		int p=in[0]-'A';
		scanf("%s",in);
		int q=in[0]-'A';
		g[p].push_back(q);
		g[q].push_back(p);
		S[i]=p;
		T[i]=q;
	}
	p3[0]=1;
	for(int i=1;i<32;i++)p3[i]=p3[i-1]*3;
	dfs(0,-1,-1,0LL,0LL,0);
	for(int i=0;i<a;i++){
		zx[i]=x[i];
		zy[i]=y[i];
	}
	std::sort(zx,zx+a);
	std::sort(zy,zy+a);
	for(int i=0;i<a;i++){
		px[i]=(lower_bound(zx,zx+a,x[i])-zx)*3;
		py[i]=(lower_bound(zy,zy+a,y[i])-zy)*3;
	}
	for(int i=0;i<100;i++)for(int j=0;j<100;j++)ret[i][j]='.';
	for(int i=0;i<a;i++){
		ret[px[i]][py[i]]='A'+i;
	}
	for(int i=0;i<a-1;i++){
		if(px[S[i]]==px[T[i]]){
			for(int j=min(py[S[i]],py[T[i]])+1;j<max(py[S[i]],py[T[i]]);j++)ret[px[S[i]]][j]='-';
		}else{
			for(int j=min(px[S[i]],px[T[i]])+1;j<max(px[S[i]],px[T[i]]);j++)ret[j][py[S[i]]]='|';
		}
	}
	printf("100 100\n");
	for(int i=0;i<100;i++)printf("%s\n",ret[i]);
}

E:
死ぬほど苦手。一生不可能。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> > g[110000];
int gcd(int a,int b){
	while(a){
		b%=a;
		int c=a;a=b;b=c;
	}
	return b;
}
int ABS(int a){return max(a,-a);}
int v[110000];
int d[110000];
int tmp=0;
void dfs(int a,int b,int c){
	//printf("%d %d %d\n",a,b,c);
	d[a]=b;
	v[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(ABS(c)==ABS(g[a][i].second))continue;
		int ad=1;
		if(g[a][i].second<0)ad=-1;
		if(!v[g[a][i].first]){
			
			dfs(g[a][i].first,b+ad,g[a][i].second);
		}else{
		//	printf("%d %d %d %d\n",a,b+1,g[a][i].first,d[g[a][i].first]);
			tmp=gcd(tmp,ABS(b+ad-d[g[a][i].first]));
		}
	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);
		g[p].push_back(make_pair(q,i+1));
		g[q].push_back(make_pair(p,-i-1));
	}
	bool dame=false;
	int ret=0;
	for(int i=0;i<a;i++){
		if(v[i])continue;
		tmp=0;
		dfs(i,0,0);
		if(!tmp){dame=true;break;}
	//	printf("%d\n",tmp);
		ret+=tmp;
	}
	if(dame)printf("-1\n");
	else printf("%d\n",ret);
}

result:
4位(□ある人2位)

苦手セットなのに順位はよかったです。