JAG 春コンテスト

wakabaです。1位でした。

自分が解いた問題だけいろいろ書いておきます。

B: Cube Coloring
気合で数えるだけ。必要な気合も少なめ。
(687Byte)

#include<stdio.h>
#include<algorithm>
using namespace std;
long long p[1100];
long long q[1100];
long long r[1100];
int ABS(int a){
	return max(a,-a);
}
int main(){
	int a,b,c,d,e,f,g;
	scanf("%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g);
	for(int i=0;i<a;i++)p[ABS(i-d)%g]++;
	for(int i=0;i<g;i++){
		int s=(e+1+g-i-1)/g;
		int t=(b-e+g-i-1)/g;
		for(int j=0;j<g;j++)q[(i+j)%g]+=p[j]*(s+t);
	}
	for(int i=0;i<g;i++)q[i]-=p[i];
	for(int i=0;i<g;i++){
		int s=(f+1+g-i-1)/g;
		int t=(c-f+g-i-1)/g;
		for(int j=0;j<g;j++)r[(i+j)%g]+=q[j]*(s+t);
	}
	for(int i=0;i<g;i++)r[i]-=q[i];
	for(int i=0;i<g;i++){
		if(i)printf(" ");
		printf("%lld",r[i]);
	}
	printf("\n");
}

E: Parentheses
上昇、下降に分けてそれぞれ前と後ろからgreedy。そもそも個数が違ったらNo,を忘れていた…
(1261Byte)

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char str[1000];
int v[1000];
int L[1000];
int R[1000];
bool used[1000];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%s",str);
		int n=strlen(str);
		int now=0;
		for(int j=0;j<n;j++){
			if(str[j]=='(')now++;
			else now--;
			L[i]=min(L[i],now);
		}
		v[i]=now;
		now=0;
		for(int j=n-1;j>=0;j--){
			if(str[j]==')')now++;
			else now--;
			R[i]=min(R[i],now);
		}
	}
	int sum=0;
	for(int i=0;i<a;i++)sum+=v[i];
	if(sum!=0){
		printf("No\n");
		return 0;
	}
	int val=0;
	for(int i=0;i<a;i++){
		int use=-1;
		int m=0;
		for(int j=0;j<a;j++){
			if(!used[j]&&v[j]>0&&val+L[j]>=0){
				if(m<v[j]){
					m=v[j];
					use=j;
				}
			}
		}
		if(~use){
			used[use]=true;
			val+=m;
		}
	}
	for(int i=0;i<a;i++){
		if(v[i]==0&&val+L[i]>=0)used[i]=true;
	}
	val=0;
	for(int i=0;i<a;i++){
		int use=-1;
		int m=0;
		for(int j=0;j<a;j++){
			if(!used[j]&&v[j]<0&&val+R[j]>=0){
				if(m<-v[j]){
					m=-v[j];
					use=j;
				}
			}
		}
		if(~use){
			used[use]=true;
			val+=m;
		}
	}
	bool ok=true;
	for(int i=0;i<a;i++)if(!used[i])ok=false;
	if(ok)printf("Yes\n");
	else printf("No\n");
}

C: Decoding Ancient Messages
でかい数で最小費用流。なるほどなあ。あとは実装をがんばる。
(2932Byte)

#include<bits/stdc++.h>
using namespace std;
typedef int wint;
struct cint{
	int num[55];
	cint(){for(int i=0;i<55;i++)num[i]=0;}
	cint operator+(const cint &a){
		cint ret;
		for(int i=0;i<55;i++)ret.num[i]=num[i]+a.num[i];
		return ret;
	}
	cint operator-(const cint &a){
		cint ret;
		for(int i=0;i<55;i++)ret.num[i]=num[i]-a.num[i];
		return ret;
	}
	cint operator-(){
		cint ret;
		for(int i=0;i<55;i++)ret.num[i]=-num[i];
		return ret;
	}
	cint operator*(const int &k){
		cint ret;
		for(int i=0;i<55;i++)ret.num[i]=num[i]*k;
		return ret;
	}
};
inline bool operator<(const cint &a,const cint &b){
	for(int i=0;i<55;i++){
		if(a.num[i]!=b.num[i])return a.num[i]<b.num[i];
	}
	return false;
}
namespace MCF{
	//お前さっき俺達がコード書いてる時、チラチラライブラリみてただろ。
}
char str[100][100];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	MCF::init(a*2+2);
	int s=a*2;
	int t=a*2+1;
	for(int i=0;i<a;i++){
		MCF::ae(s,i,1,cint());
		MCF::ae(a+i,t,1,cint());
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			cint val;
			if('A'<=str[i][j]&&str[i][j]<='Z')val.num[str[i][j]-'A']--;
			else val.num[str[i][j]-'a'+26]--;
			MCF::ae(i,a+j,1,val);
		}
	}
	MCF::solve(s,t,a);
	for(int i=0;i<52;i++){
		for(int j=0;j<-(MCF::toc.num[i]);j++){
			if(i<26)printf("%c",'A'+i);
			else printf("%c",'a'+i-26);
		}
	}
	printf("\n");
}

F: Polygon Guards
まず幾何をする。答えはどうせ10頂点以下だろうから適当に探索すれば間に合いそう*1。ひたすら実装する。
(3272Byte)

#include<bits/stdc++.h>
using namespace std;
//あ、お前さ木村さ、さっき俺達がコッ、コード出した時さ、なかなかAC来なかったよな？
//そうだよ
//見たけりゃライブラリ見せてやるよ、ほら、見ろよ見ろよ
int g[100][100];
long long to[100];
Pt poly[100];
int wolf;
int N;
int dfs(int a,int b,long long c){
	if(a==N){
		if(c==(1LL<<N)-1)return 1;
		return 0;
	}
	int val=dfs(a+1,b,c);
	if(val)return 1;
	
	if(b==wolf)return 0;
	
	val=dfs(a+1,b+1,c|to[a]);
	
	if(val)return 1;
	return 0;
}
int X[100];
int Y[100];
pair<double,Pt> pts[1000];
int main(){
	int a;
	scanf("%d",&a);
	N=a;
	for(int i=0;i<a;i++)scanf("%d%d",X+i,Y+i);
	for(int i=0;i<a;i++)g[i][i]=1;
	for(int i=0;i<a;i++)poly[i]=Pt(X[i],Y[i]);
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++){
			if(i==j)continue;
			int sz=0;
			
			//printf("%d %d:\n",i,j);
			for(int k=0;k<a;k++){
				if(iLL(poly[i],poly[j],poly[k],poly[(k+1)%a])!=-1&&iSS(poly[i],poly[j],poly[k],poly[(k+1)%a])){
					Pt point=pLL(poly[i],poly[j],poly[k],poly[(k+1)%a]);
					pts[sz++]=make_pair(point.x*114514+point.y,point);
				}
			}
			if(sz<2){
				g[i][j]=1;
				continue;
			}
			std::sort(pts,pts+sz);
			bool ok=true;
			for(int k=0;k<sz-1;k++){
				Pt M=(pts[k].second+pts[k+1].second)/2.0;
				//printf("(%f, %f)",M.x,M.y);
				if(!~sGP(a,poly,M)){
					ok=false;
				//	printf("---!!!---");
				}
				//printf("\n");
			}
			if(ok)g[i][j]=1;
		}
	
	//for(int i=0;i<a;i++){
	//	for(int j=0;j<a;j++)printf("%d ",g[i][j]);
	//	printf("\n");
	//}
	for(int i=0;i<a;i++)
		for(int j=0;j<a;j++)
			if(g[i][j])to[i]+=(1LL<<j);
	for(int i=1;i<=9;i++){
		wolf=i;
		if(dfs(0,0,0)){
			printf("%d\n",i);
			return 0;
		}
	}
	printf("10\n");
}

以上です。

*1:実際は9頂点以下らしいです