Codeforces Round #360 (Div. 1)

初全完。全完ゲーはHack上乗せ勝負なのでVirtual Participation勢には不利。

A	B	C	D	E	Place
00:07	00:17 (+1)	00:27	00:50	01:39	16th

A:
よくある二色塗りのUFを書いたら他の人に取り残されたんだけど、簡単な解法があるのかな。

#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 UF[210000];
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>A;
vector<int>B;
int v[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a*2;i++)UF[i]=-1;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		UNION(p,q+a);
		UNION(q,p+a);
	}
	for(int i=0;i<a;i++){
		if(FIND(i)==FIND(i+a)){
			printf("-1\n");return 0;
		}
	}
	for(int i=0;i<a;i++){
		if(v[FIND(i)]==0&&v[FIND(i+a)]==0){
			v[FIND(i)]=1;
			v[FIND(i+a)]=-1;
			A.push_back(i);
		}else{
			if(v[FIND(i)]==1||v[FIND(i+a)]==-1){
				v[FIND(i)]=1;
				v[FIND(i+a)]=-1;
				A.push_back(i);
			}else{
				v[FIND(i)]=-1;
				v[FIND(i+a)]=1;
				B.push_back(i);
			}
		}
	}
	printf("%d\n",(int)A.size());
	for(int i=0;i<A.size();i++){
		if(i)printf(" ");printf("%d",A[i]+1);
	}
	printf("\n");
	printf("%d\n",(int)B.size());
	for(int i=0;i<B.size();i++){
		if(i)printf(" ");printf("%d",B[i]+1);
	}
	printf("\n");
}

B:
素因数が足りてるか。素数でないものを見てしまい1WA。

#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[1100000];
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;
}
vector<pair<int,int> > v;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=2;i<=b;i++){
		if(b%i)continue;
		int e=0;
		while(b%i==0){
			e++;
			b/=i;
		}
		v.push_back(make_pair(i,e));
	}
	bool ok=true;
	for(int i=0;i<v.size();i++){
		bool OK=false;
		for(int j=0;j<a;j++){
			int tmp=c[j];
			int cur=0;
			while(tmp%v[i].first==0){
				tmp/=v[i].first;
				cur++;
			}
			if(cur>=v[i].second){
				OK=true;break;
			}
		}
		if(!OK){ok=false;break;}
	}
	if(ok)printf("Yes\n");
	else printf("No\n");
}

C:
合計をKにする用としなくてもいい用の2つの要素があればよい。これも上位勢は速すぎ

#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 dp[510][510];
int c[510];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	vector<int>ans;
	dp[0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=b;j>=0;j--){
			for(int k=b;k>=0;k--){
				if(dp[j][k]){
					if(j+c[i]<=b){
						dp[j+c[i]][k+c[i]]=1;
						dp[j+c[i]][k]=1;
					}
				}
			}
		}
	}
	for(int i=0;i<=b;i++)if(dp[b][i])ans.push_back(i);
	printf("%d\n",(int)ans.size());
	for(int i=0;i<ans.size();i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}

D:
強引にunion findの自明解を送ったら5974ms/6000msで通ってしまった...。非再帰Union-Findにすればもっと速くなるのではないかと考えると、Time Limitが雑すぎる。
どうせ想定解も変なsqrtテクか永続あたりを使ってオーダー落とすUnion-Findなんでしょ。

#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 dp[510][510];
int c[510];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	vector<int>ans;
	dp[0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=b;j>=0;j--){
			for(int k=b;k>=0;k--){
				if(dp[j][k]){
					if(j+c[i]<=b){
						dp[j+c[i]][k+c[i]]=1;
						dp[j+c[i]][k]=1;
					}
				}
			}
		}
	}
	for(int i=0;i<=b;i++)if(dp[b][i])ans.push_back(i);
	printf("%d\n",(int)ans.size());
	for(int i=0;i<ans.size();i++){
		if(i)printf(" ");
		printf("%d",ans[i]);
	}
	printf("\n");
}

E:
それぞれの頂点からスタートして自分に戻るループの最小長を求めて置いて、短いものから逆にたどっていくgreedy。強連結成分分解のライブラリは作りましょう......

#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[5100];
vector<int>rev[5100];
int v[5100];
int num[5100];
int conv[5100];
int scc[5100];
int fi[5100];
int ss[5100];
int cur;
void dfs(int a){
	for(int i=0;i<g[a].size();i++){
		if(v[g[a][i]])continue;
		v[g[a][i]]=1;
		dfs(g[a][i]);
	}
	conv[a]=cur;
	num[cur++]=a;
}
void dfs2(int a){
	scc[a]=cur;
	ss[cur]++;
	for(int i=0;i<rev[a].size();i++){
		if(v[rev[a][i]])continue;
		v[rev[a][i]]=1;
		dfs2(rev[a][i]);
	}
}
int len[5100];
int dp[2][5100];
int st;
void dfs3(int a,int b){
	v[a]=1;
	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==st){
			if(len[st]==-1)len[st]=b+1;
			else if(len[st]>b+1)len[st]=b+1;
		}
		if(v[g[a][i]])continue;
		dfs3(g[a][i],b+1);
	}
}
vector<int>G[5100];
int g2[5100][5100];
int used[5100];
pair<pair<int,int>,int> q[5100];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		rev[q].push_back(p);
	}
	for(int i=0;i<a;i++){
		if(v[i])continue;
		v[i]=1;
		dfs(i);
	}
	cur=0;
	for(int i=0;i<a;i++)v[i]=0;
	for(int i=a-1;i>=0;i--){
		if(v[num[i]])continue;
		v[num[i]]=1;
		fi[cur]=num[i];
		dfs2(num[i]);
		cur++;
	}
	for(int i=0;i<a;i++){
		len[i]=-1;
		st=i;
		for(int j=0;j<a;j++)v[j]=0;

		dfs3(i,0);
	//printf("%d: %d\n",i,len[i]);
		q[i]=make_pair(make_pair(len[i],conv[i]),i);
	}
	std::sort(q,q+a);
	for(int i=0;i<a;i++){
		for(int j=0;j<rev[i].size();j++){
			if(scc[i]!=scc[rev[i][j]]){
				g2[scc[i]][scc[rev[i][j]]]=1;
			}
		}
	}
	for(int i=0;i<cur;i++){
		for(int j=0;j<cur;j++){
			if(g2[i][j])G[i].push_back(j);
		}
	}
	int ret=0;
	for(int i=0;i<a;i++){
		int at=q[i].second;
		int cost=q[i].first.first;
		if(used[scc[at]])continue;
		if(cost!=-1){
			ret+=998*cost+1;
		}
		used[scc[at]]=1;
		queue<int>Q;
		Q.push(scc[at]);
		while(Q.size()){
			int now=Q.front();Q.pop();
			ret+=ss[now];
			for(int j=0;j<G[now].size();j++){
				if(used[G[now][j]])continue;
				used[G[now][j]]=1;
				Q.push(G[now][j]);
			}
		}
	}
	printf("%d\n",ret);
}