Codeforces Round #383 (Div. 1)

A	B	C	D	E	Place
00:06	00:14	01:03 (+1)	(-2)	-	35th

悪くはないと思うんだけどね......

A:
サイクルさがしてLCM.

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[110];
long long gcd(long long a,long long b){
	while(a){
		b%=a;swap(a,b);
	}
	return b;
}
long long lcm(long long a,long long b){
	return a/gcd(a,b)*b;
}
int v[110];
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++)b[i]--;
	long long ret=1;
	for(int i=0;i<a;i++){
		if(v[i])continue;
		int at=i;
		v[at]=1;
		int cnt=0;
		while(1){
			at=b[at];
			cnt++;
			if(v[at]){
				if(at==i)break;
				else{
					printf("-1\n");return 0;
				}
			}
			v[at]=1;
		}
		if(cnt%2==0)cnt/=2;
		ret=lcm(ret,cnt);
	}
	printf("%I64d\n",ret);
}

B:
こんなやるだけ典型もういらないから

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int UF[1100];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
vector<int>v[1100];
int p[1100];
int q[1100];
int dp[1100][1100];
int main(){
	int a,b,c;scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		scanf("%d",p+i);
	}
	for(int i=0;i<a;i++){
		scanf("%d",q+i);
	}
	for(int i=0;i<a;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int s,t;scanf("%d%d",&s,&t);s--;t--;UNION(s,t);
	}
	for(int i=0;i<a;i++){
		v[FIND(i)].push_back(i);
	}
	for(int i=0;i<1100;i++)for(int j=0;j<1100;j++)dp[i][j]=-mod;
	dp[0][0]=0;
	for(int i=0;i<a;i++){
		int W=0;
		int B=0;
		for(int j=0;j<v[i].size();j++){
			W+=p[v[i][j]];
			B+=q[v[i][j]];
		}
		for(int j=0;j<=c;j++){
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			if(j+W<=c)dp[i+1][j+W]=max(dp[i+1][j+W],dp[i][j]+B);
			for(int k=0;k<v[i].size();k++){
				if(j+p[v[i][k]]<=c)dp[i+1][j+p[v[i][k]]]=max(dp[i+1][j+p[v[i][k]]],dp[i][j]+q[v[i][k]]);
			}
		}
	}
	int ret=0;
	for(int i=0;i<=c;i++)ret=max(ret,dp[a][i]);
	printf("%d\n",ret);
}

C:
一発ネタ。「偶数と奇数は別の色」に制約を強める(これは真に強い)と途端に簡単になる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int UF[410000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int A[110000];
int B[110000];
int ans[410000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<4*a;i++)UF[i]=-1;
	int F=a*2;
	for(int i=0;i<a;i++){
		UNION(i*2,i*2+1+F);
		UNION(i*2+F,i*2+1);
	}
	for(int i=0;i<a;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		A[i]=p;B[i]=q;
		UNION(p,q+F);
		UNION(q,p+F);
	}
	for(int i=0;i<4*a;i++)ans[i]=-1;
	for(int i=0;i<a;i++){
		int f=ans[FIND(A[i])];
		if(f<0){
			ans[FIND(A[i])]=0;
			ans[FIND(A[i]+F)]=1;
			f=0;
		}
		printf("%d %d\n",f+1,(!f)+1);
	}
}

D:
dsuというCFでは頻出のアルゴリズムらしい。慣れてないアルゴリズムは実装しててもどこが悪いのかわからなくて嵌り続ける。
結局部分木のサイズを計算するのが間違っていた......

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<pair<int,char> >g[510000];
char in[510000];
int ans[510000];
int dep[510000];
int sz[510000];
int key[510000];
void dfs(int a){
	sz[a]=1;
	for(int i=0;i<g[a].size();i++){
		dep[g[a][i].first]=dep[a]+1;
		key[g[a][i].first]=key[a]^(1<<(g[a][i].second-'a'));
		dfs(g[a][i].first);
		
		sz[a]+=sz[g[a][i].first];
	}
}
int wolf[1<<22];
vector<int>del;
vector<int>vis;
void dfs2(int a,int b){
	for(int i=0;i<g[a].size();i++){
		dfs2(g[a][i].first,b);
	}
	for(int k=0;k<23;k++){
		int x=key[a];
		if(k<22)x^=(1<<k);
		ans[b]=max(ans[b],dep[a]+wolf[x]-2*dep[b]);
	}
}
void dfs3(int a){
	for(int i=0;i<g[a].size();i++){
		dfs3(g[a][i].first);
	}
	if(wolf[key[a]]<0)del.push_back(key[a]);
	wolf[key[a]]=max(wolf[key[a]],dep[a]);
}
void calc(int a){
	int lc=-1;
	int val=-1;
	for(int i=0;i<g[a].size();i++){
		if(val<sz[g[a][i].first]){
			lc=g[a][i].first;
			val=sz[g[a][i].first];
		}
	}
	for(int i=0;i<g[a].size();i++){
		if(g[a][i].first==lc)continue;
		calc(g[a][i].first);
		for(int j=0;j<del.size();j++){
			wolf[del[j]]=-mod;
		}
		del.clear();
	}
	if(~lc){
		calc(lc);
		for(int i=0;i<g[a].size();i++){
			if(g[a][i].first!=lc){
				dfs2(g[a][i].first,a);
				dfs3(g[a][i].first);
			}
		}
	}
	for(int i=0;i<23;i++){
		int x=key[a];
		if(i<22)x^=(1<<i);
		ans[a]=max(ans[a],dep[a]+wolf[x]-dep[a]*2);
	}

	if(wolf[key[a]]<0)del.push_back(key[a]);
	wolf[key[a]]=max(wolf[key[a]],dep[a]);
	
	for(int i=0;i<g[a].size();i++)ans[a]=max(ans[a],ans[g[a][i].first]);
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a-1;i++){
		int p;
		scanf("%d%s",&p,in+i);
		p--;
		g[p].push_back(make_pair(i+1,in[i]));
	}
	dfs(0);
	for(int i=0;i<(1<<22);i++)wolf[i]=-mod;
	calc(0);
	
	for(int i=0;i<a;i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}