Codeforces Round #362 (Div. 1)

解けたのに虚しくなる意味不明なセット。面白くはない。

A	B	C	D	E	F	Place
00:10 (+1)	00:17	00:38	01:14	-	-	37th

A:
辺を全部mapで更新する。何も考えずにやったらオーバーフローした。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
map<long long,long long> m;
long long u[110];
long long v[110];
int main(){
	int a;scanf("%d",&a);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			long long p,q,r;scanf("%I64d%I64d%I64d",&p,&q,&r);
			int sa=0;
			int sb=0;
			while(p){
				u[sa++]=p;
				p/=2;
			}
			while(q){
				v[sb++]=q;
				q/=2;
			}
			int sl=0;
			for(int i=0;i<min(sa,sb);i++){
				if(u[sa-1-i]==v[sb-1-i])sl++;
				else break;
			}
			for(int i=0;i<sa-sl;i++){
				m[u[i]]+=r;
			}
			for(int i=0;i<sb-sl;i++){
				m[v[i]]+=r;
			}
		}else{
			long long p,q;scanf("%I64d%I64d",&p,&q);
			int sa=0;
			int sb=0;
			while(p){
				u[sa++]=p;
				p/=2;
			}
			while(q){
				v[sb++]=q;
				q/=2;
			}
			int sl=0;
			long long ret=0;
			for(int i=0;i<min(sa,sb);i++){
				if(u[sa-1-i]==v[sb-1-i])sl++;
				else break;
			}
			for(int i=0;i<sa-sl;i++){
				if(m.count(u[i]))ret+=m[u[i]];
			}
			for(int i=0;i<sb-sl;i++){
				if(m.count(v[i]))ret+=m[v[i]];
			}
			printf("%I64d\n",ret);
		}
	}
}

B:
いい加減こういうの見飽きた。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[110000];
int sz[110000];
double dp[110000];
void dfs(int a){
	sz[a]=1;
	for(int i=0;i<g[a].size();i++){
		dfs(g[a][i]);
		sz[a]+=sz[g[a][i]];
	}
}
void calc(int a,double b){
	dp[a]=b;
	for(int i=0;i<g[a].size();i++){
		calc(g[a][i],b+1+(sz[a]-1-sz[g[a][i]])*0.5);
	}
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p;scanf("%d",&p);p--;
		g[p].push_back(i+1);
	}
	dfs(0);
	calc(0,0);
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%.12f",dp[i]+1);
	}
	printf("\n");
}

C:
手で数学をするだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
long long b[110000];
long long d3=(mod+1)/3;
long long d2=(mod+1)/2;
long long pw(long long a,long long b){
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		b/=2;
		a=a*a%mod;
	}
	return ret;
}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%I64d",b+i);
	bool gu=false;
	for(int i=0;i<a;i++)if(b[i]%2==0)gu=true;
	long long tmp=pw(2,b[0]);
	for(int i=1;i<a;i++)tmp=pw(tmp,b[i]);
	tmp=tmp*d2%mod;
	long long bs;
	if(gu)bs=(tmp+1)%mod;
	else bs=(tmp+mod-1)%mod;
	bs=bs*d3%mod;
	printf("%d/%d\n",(int)bs,(int)tmp);
}

D:
Trie上でCow Relaysするだけ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[210];
char in[210][210];
int len[210];
struct Trie{
	int chi[26];
	int sc;
	Trie(){for(int i=0;i<26;i++)chi[i]=-1;sc=0;}
};
Trie pool[210];
char st[210];
int n;
int to[210][26];
void dfs(int a,int b){
	for(int i=0;i<26;i++){
		if(pool[a].chi[i]==-1)continue;
		st[b]='a'+i;
		dfs(pool[a].chi[i],b+1);
	}
	for(int i=0;i<n;i++){
		if(len[i]>b)continue;
		bool ok=true;
		for(int j=0;j<len[i];j++){
			if(in[i][len[i]-1-j]!=st[b-1-j]){ok=false;break;}
		}
		if(ok)pool[a].sc+=c[i];
	}
	for(int i=0;i<26;i++){
		st[b]=i+'a';
		bool ok=false;
		for(int j=0;j<=b;j++){
			int now=0;
			for(int k=j;k<=b;k++){
				if(pool[now].chi[st[k]-'a']==-1){now=-1;break;}
				now=pool[now].chi[st[k]-'a'];
			}
			if(now!=-1){
				ok=true;to[a][i]=now;break;
			}
		}
		if(!ok)to[a][i]=0;
	}
}
long long dp[210][210][210];
long long val[210][410];
long long las[210][210];
int main(){
	int a;
	long long b;
	scanf("%d%I64d",&a,&b);
	n=a;
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<a;i++){
		scanf("%s",in[i]);
		len[i]=strlen(in[i]);
	}
	int sz=1;
	for(int i=0;i<a;i++){
		int at=0;
		for(int j=0;in[i][j];j++){
			if(pool[at].chi[in[i][j]-'a']==-1){
				pool[at].chi[in[i][j]-'a']=sz++;
				at=sz-1;
			}else at=pool[at].chi[in[i][j]-'a'];
		}
	}
	dfs(0,0);
	for(int i=0;i<sz;i++){
		for(int j=0;j<210;j++)for(int k=0;k<210;k++)dp[i][j][k]=-mod;
		dp[i][0][i]=0;
		for(int j=0;j<sz;j++){
			for(int k=0;k<sz;k++){
				for(int l=0;l<26;l++){
					dp[i][j+1][to[k][l]]=max(dp[i][j+1][to[k][l]],dp[i][j][k]+pool[to[k][l]].sc);
				}
			}
		}
	}
	long long ret=0;
	for(int i=0;i<sz;i++){
		for(int j=0;j<410;j++){
			val[i][j]=-inf;
			if(b-j<0)continue;
			for(int k=1;k<=sz;k++){
				if(dp[i][k][i]<0)continue;
				val[i][j]=max(val[i][j],(b-j)/k*dp[i][k][i]);
			}
		}
	}
	if(b<sz){
		for(int i=0;i<sz;i++)ret=max(ret,dp[0][b][i]);
		printf("%I64d\n",ret);
		return 0;
	}
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++){
			las[i][j]=-inf;
			for(int k=0;k<sz;k++)las[i][j]=max(las[i][j],dp[i][j][k]);
		}
	}
	for(int i=0;i<sz;i++){
		for(int j=0;j<sz;j++)for(int k=0;k<sz;k++){
			ret=max(ret,dp[0][j][i]+val[i][j+k]+las[i][k]);
		}
	}
	printf("%I64d\n",ret);
}

F:
二分探索で、中でそれぞれの辺から中に伸ばすとどの範囲なら対応可能かというのを求めておけば、ある辺からスタートするとどこまでいけるかというのがわかり、判断可能でO(N^2 log X)なんだろうけど、実装量も多すぎるし、JAGの幾何と同様全く面白くない。