【Codeforces #131 Div2】Solutions

9135 ワード
codeforces
【A System of Equations】
　　 http://www.codeforces.com/contest/214/problem/A
n,mを与えて、どれだけの二元グループ(a,b)がを満たしているかを聞いて、その中のa,b>0.
nは小さいので,a,bの値を直接列挙すればよい,複雑度O(n²). 
#include <iostream>

using namespace std;

int n,m;

long long ans=0;

int main(){

	cin>>n>>m;

	for(int i=0;i<=1000;i++)

		for(int j=0;j<=1000;j++)

			if(i*i+j==n && i+j*j==m) ans++;

	cout<<ans<<endl;

	return 0;

}

 
【B Hometask】
　　 http://www.codeforces.com/contest/214/problem/B
n個の数字を与えて、このn個の数字の中のいくつかで1つの新しい数字につづることを要求して、新しい数字が2,3,5で除けることができて、しかも新しい数字はできるだけ大きいです.
同時に2,5で割り切れる場合は,末尾は0でなければならないので,無解を排除することができる.
3で割り切れるようになると、1桁の数字を合わせると3の整数倍にならなければなりません.
もし数字が0であれば、まず0から新しい数字のビットに置いて、問題はできるだけ少ない数(つまりできるだけ多い数を選ぶ)を除いて、和が3で割り切れるように変換します.
まず、すべての数字が選択されていると仮定し、sum、sum型3の3つの場合があります.
1)sum mod 3=0数字を大きくから小さく並べ替えるとよい.
2)sum mod 3=1①数列から1つの数xを除去し、x mod 3=1とする.
②1が実現できなければ2つの数i,jを除去し、(i+j)mod 3=1とする.
3)sum mod 3=2①数列から1つの数xを除去し、x mod 3=2とする.
②1が実現できなければ2つの数i,jを除去し、(i+j)mod 3=2とする.
残りの数列は条件に合っています.
なぜ最大2つの数を削除すれば要求に合致するのか、より多くの数を削除するのか.
i,j,k,(i+j+k)mod 3=m(m=0,1,2)が存在すると,必ずx∈(i,j,k)が存在し,x≡(i+j+k)(mod 3)が存在するので,この場合は1つの数を削除するだけであることが証明される.
コードは見苦しくて、考えに重点を置いています......
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

using namespace std;

int a[100010],n;

long long sum=0;

bool flag=false;

int vis[100];

int main(){

	cin>>n;

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		vis[a[i]]++;

		sum+=a[i];

		if(!a[i]) flag=true;

	}

	if(!sum){

		cout<<"0"<<endl;

		return 0;

	}

	if(!flag){

		cout<<"-1"<<endl;

		return 0;

	}

	sort(a+1,a+1+n,greater<int>());

	int delta=sum%3;

	if(!delta){

		for(int i=1;i<=n;i++) printf("%d",a[i]);

		cout<<endl;

		return 0;

	}else if(delta==1){

		for(int i=1;i<=9;i++)

			if(vis[i] && i%3==1){

				for(int j=1;j<=n;j++)

					if(a[j]==i){a[j]=0;break;}

				sum-=i;

				if(!sum){

					cout<<"0"<<endl;

					return 0;

				}

				sort(a+1,a+1+n,greater<int>());

				for(int i=1;i<n;i++) printf("%d",a[i]);

				cout<<endl;

				return 0;

			}

		for(int i=1;i<=9;i++)

			for(int j=1;j<=9;j++)

				if((i+j)%3==1){

					if(i==j && vis[i]>1){

						for(int k=1;k<=n;k++)

							if(a[k]==i){a[k]=0,a[k+1]=0;break;}

						sum=sum-2*i;

						if(!sum){

							cout<<"0"<<endl;

							return 0;

						}

						sort(a+1,a+1+n,greater<int>());

						for(int i=1;i<n-1;i++) printf("%d",a[i]);

						cout<<endl;

						return 0;

					}else if(i!=j && vis[i] && vis[j]){

						for(int k=1;k<=n;k++)

							if(a[k]==i){a[k]=0;break;}

						for(int k=1;k<=n;k++)

							if(a[k]==j){a[k]=0;break;}

						sum-=i,sum-=j;

						if(!sum){

							cout<<"0"<<endl;

							return 0;

						}

						sort(a+1,a+1+n,greater<int>());

						for(int i=1;i<n-1;i++) printf("%d",a[i]);

						cout<<endl;

						return 0;

					}

				}

	}else if(delta==2){

		for(int i=1;i<=9;i++)

			if(vis[i] && i%3==2){

				for(int j=1;j<=n;j++)

					if(a[j]==i){a[j]=0;break;}

				sum-=i;

				if(!sum){

					cout<<"0"<<endl;

					return 0;

				}

				sort(a+1,a+1+n,greater<int>());

				for(int i=1;i<n;i++) printf("%d",a[i]);

				cout<<endl;

				return 0;

			}

		for(int i=1;i<=9;i++)

			for(int j=1;j<=9;j++)

				if((i+j)%3==2){

					if(i==j && vis[i]>1){

						for(int k=1;k<=n;k++)

							if(a[k]==i){a[k]=0,a[k+1]=0;break;}

							sum=sum-2*i;

						if(!sum){

							cout<<"0"<<endl;

							return 0;

						}

						sort(a+1,a+1+n,greater<int>());

						for(int i=1;i<n-1;i++) printf("%d",a[i]);

						cout<<endl;

						return 0;

					}else if(i!=j && vis[i] && vis[j]){

						for(int k=1;k<=n;k++)

							if(a[k]==i){a[k]=0;break;}

						for(int k=1;k<=n;k++)

							if(a[k]==j){a[k]=0;break;}

						sum-=i,sum-=j;

						if(!sum){

							cout<<"0"<<endl;

							return 0;

						}

						sort(a+1,a+1+n,greater<int>());

						for(int i=1;i<n-1;i++) printf("%d",a[i]);

						cout<<endl;

						return 0;

					}

				}

	}

	cout<<"-1"<<endl;

	return 0;

}

 
【C Game】
　　 http://www.codeforces.com/contest/214/problem/C
n個の仕事は3台のコンピュータがあって、i個目の仕事はci台のコンピュータの上で完成する必要があります.各作業には「親作業」がたくさんあり、「親作業」が完了してから開始する必要があります.仕事は1の时间を费やして、コンピュータを交换するのも时间を必要として、具体的にテーマの说明を见て、最も良い策略の最短时间にすべての仕事を完成することを闻きます.
一見面倒なDP問題ですが、よく考えてみるとこれがお父さんですね......3台のパソコン1→2、2→3、3→1の時間はすべて1で、他の移動時間は2です.つまり、1→3を考えたら、1→2→3に及ばないと思います.後者は2番のパソコンが必要な仕事をついでにすることができます.その他の移動は同じです.この点がわかると、これは欲張りな問題になります.パソコンは1→2→3→1→2の順番で入れ替わり、できる仕事はやり、最初のパソコンを列挙すればいいのです.
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

template<class T>inline void gmin(T &a,T b){if(a>b)a=b;}



int n,k,x,c[201],map[201][201],deg[201],tmp[201],ans=2147483647;



int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%d",&c[i]);

	for(int i=1;i<=n;i++){

		scanf("%d",&k);

		while(k--){

			scanf("%d",&x);

			map[x][i]=1;

			tmp[i]++;

		}

	}

	for(int first_c=1;first_c<=3;first_c++){

		int cur=first_c,rest=n,res=0;

		memcpy(deg,tmp,sizeof(deg));

		while(rest){

			for(int k=1;k<=n;k++){

				for(int i=1;i<=n;i++)

					if(!deg[i] && c[i]==cur){

						for(int j=1;j<=n;j++)

							if(map[i][j]) deg[j]--;

					deg[i]--,rest--;

				}

			}

			cur=cur%3+1;

			if(rest) res++;

		}

		gmin(ans,res);

	}

	ans+=n;

	printf("%d
",ans);

	return 0;

}

 
【D Numbers】
　　 http://www.codeforces.com/contest/214/problem/D
また、FurikとRubikはnを与え、a[]を与え、nビットを超えない長さの新しい数字を構築することを要求し、iは少なくともa[i]回新しい数字に現れる.このような数がいくつあるかを聞く.
比較的簡単な数桁統計問題で、長さが1桁増えるごとに、1つの数字を挿入して、組み合わせ数で求めます.
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;



long long const BASE=1000000007ll;

int n,a[11],sum;

long long ans=0,f[11][101],C[101][101];



long long dp(int x){

	memset(f,0,sizeof(f));

	f[0][0]=1;

	for(int i=0;i<10;i++)

		for(int j=0;j<=x;j++)

			if(!f[i][j]) continue;

			else

				for(int k=a[i+1];k+j<=x;k++)

					f[i+1][j+k]=(f[i+1][j+k]+f[i][j]*C[j+k][k])%BASE;

	return f[10][x];

}



int main(){

	scanf("%d",&n);

	for(int i=1;i<=10;i++){

		scanf("%d",&a[i]);

		sum+=a[i];

	}

	C[0][0]=1;

	for(int i=1;i<=n;i++){

		C[i][0]=1;

		for(int j=1;j<=i;j++)

			C[i][j]=(C[i-1][j]+C[i-1][j-1])%BASE;

	}

	for(int bit=max(1,sum);bit<=n;bit++){

		if(bit==1) ans+=sum==1?1:9;

		else{

			for(int i=2;i<=10;i++){

				int tmp=(a[i]!=0);

				a[i]-=tmp;

				ans=(ans+dp(bit-1))%BASE;

				a[i]+=tmp;

			}

		}

	}

	cout<<ans<<endl;

	return 0;

}

 
【E Relay Race】
　　 http://www.codeforces.com/contest/214/problem/E
一つのn×nの行列は,(1,1)~(n,n)への2つの経路を探して重み値と最大にする.各格子の重み値は1回のみ計算され、重み値には負の値があります.
その時は料金を貼って流し終わったのですが・・・夜中のうとうとして書く気になれませんでした・・・
できない参考NOIP 2000はグループの格子の数を高めます
f[k][i][j]はkステップを歩いたことを示し、Aはi行目、Bはj行目、A、Bの具体的な座標は行数とステップ数で推定することができ、これで3次元に圧縮されて過ぎてしまう.
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;



int f[601][301][301],a[301][301],n;



int max(int a,int b){

	if(a>b) return a;

	return b;

}



int gmax(int a,int b,int c,int d){

	return max(max(max(a,b),c),d);

}



int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	memset(f,0xf3,sizeof(f));

	f[1][1][1]=a[1][1];

	for(int k=2;k<=n*2-1;k++)

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				f[k][i][j]=gmax(f[k-1][i][j],f[k-1][i][j-1],f[k-1][i-1][j],f[k-1][i-1][j-1]),

				f[k][i][j]+=a[i][k-i+1]+(i==j?0:a[j][k-j+1]);

	printf("%d
",f[2*n-1][n][n]);

	return 0;

}

ActiveRecordで多階層カテゴリ
MySQL 5.6からDATETIMEは小数点以下が四捨五入(round)されるので気を付けよう