Codeforces Round #202 (Div. 1)

最近CFがやたらと好調。

A:
二分探索した。どうとでもなるらしい。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[100100];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	long long left=0LL;
	long long right=1000000000000LL;
	while(left+1<right){
		long long M=(left+right)/2;
		long long now=0;
		bool ok=true;
		for(int i=0;i<a;i++){
			if(M<b[i])ok=false;
			now+=M-b[i];
		}
		if(ok&&M<=now){
			right=M;
		}else left=M;
	}
	printf("%I64d\n",right);
}

B:
木DP。あんまり好きじゃないし、時間がかかる。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int b[100010];
vector<int> g[100010];
long long dp1[100010];
long long dp2[100010];
long long gcd(long long a,long long b){
	while(b){
		a%=b;
		long long c=a;
		a=b;
		b=c;
	}
	return a;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
long long INF=10000000000000LL;
void dfs(int a,int b){
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]!=b)dfs(g[a][i],a);
	}
	if(a&&g[a].size()==1){
		return ;
	}
	long long now=1;
	bool dame=false;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		long long t=gcd(now,dp2[g[a][i]]);
		if(INF/now+1<dp2[g[a][i]]/t){
			dame=true;
			break;
		}
		now=lcm(now,dp2[g[a][i]]);
	}
	if(dame){
		dp1[a]=dp2[a]=-1;
		return ;
	}
	int d=g[a].size();
	if(a)d--;
	dp2[a]=now*d;
	long long K=INF;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		K=min(K,dp1[g[a][i]]/now*now);
	}
	dp1[a]=K*d;
//	printf("%d %d %d\n",a,dp1[a],dp2[a]);
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",b+i);
	for(int i=0;i<a;i++)dp1[i]=b[i];
	for(int i=0;i<a-1;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<a;i++)dp2[i]=1;
	dfs(0,-1);
	bool ok=true;
	long long ret=0;
	for(int i=0;i<a;i++){
		ret+=b[i];
		if(!~dp1[i])ok=false;
	}
	if(ok)ret-=dp1[0];
	printf("%I64d\n",ret);
}

C:
落ちすぎ。直す気が起こらない。

D:
例の定理やるだけ。簡単すぎる。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[3010][3010];
int mod=1000000007;
int dp[3010][3010];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%s",str[i]);
	}
	if(str[0][1]=='#'||str[1][0]=='#'){printf("0\n");return 0;}
	dp[1][0]=1;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(i<a-1&&str[i+1][j]!='#'){
				dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
			}
			if(j<b-1&&str[i][j+1]!='#'){
				dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
			}
		}
	}
	long long A=dp[a-1][b-2];
	long long B=dp[a-2][b-1];
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			dp[i][j]=0;
	dp[0][1]=1;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(i<a-1&&str[i+1][j]!='#'){
				dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
			}
			if(j<b-1&&str[i][j+1]!='#'){
				dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
			}
		}
	}
	long long C=dp[a-1][b-2];
	long long D=dp[a-2][b-1];
	printf("%d\n",(int)((A*D-B*C)%mod+mod)%mod);
}

E:
知るか。

488 + 780 + 0 + 1808 + 0 = 3076 (3rd)
Rating: 1909 -> 2093

これはDに救われていますね…。そろそろ赤なので頑張ります。