読者です 読者をやめる 読者になる 読者になる

Codeforces Round #382 (Div. 1)

Codeforces

結果もあれだがひどいセット。

A B C D E Place
00:09 (+1) 00:16 01:02 (+1) (-1) - 57th

A:
Fibonnacci heapのあの図みたいな配置。2^nではない。

#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 main(){
	long long a;scanf("%I64d",&a);
	int ret=0;
	while(a>1){
		ret++;a=(a+1)/2;
	}
	printf("%d\n",ret);
}

B:
ゴールドバッハから偶数の答えの最大は2。奇数は3引けば同様に最大3。あとは素数判定で場合分け。
プログラミングとは

#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;
bool pr(int a){
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
int main(){
	int a;scanf("%d",&a);
	if(a%2==0){
		if(a==2)printf("1\n");
		else printf("2\n");return 0;
	}
	if(pr(a))printf("1\n");
	else if(pr(a-2))printf("2\n");
	else printf("3\n");
}

C:
このセットでは珍しくプログラミング要素だが、ただ遷移が複雑でつらいだけの木DP。

#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 K;
long long dp[110][23][23];
vector<int>g[110];
long long dp2[110][23][23];
void calc(int a,int b){
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		calc(g[a][i],a);
	}
	int t=0;
	for(int i=0;i<110;i++)for(int j=0;j<23;j++)for(int k=0;k<23;k++)dp2[i][j][k]=0;
	dp2[0][K+1][1]=1;
	dp2[0][0][0]=1;
	
	for(int i=0;i<g[a].size();i++){
		if(b==g[a][i])continue;
		for(int j=0;j<=K+1;j++){
			for(int k=0;k<=K;k++){
				if(!dp2[t][j][k])continue;
				for(int l=0;l<=K+1;l++)for(int m=0;m<=K;m++){
					if(!dp[g[a][i]][l][m])continue;
					int tj=j;int tk=k;
					tj=min(tj,l+1);
					if(tj+k-1<=K)tk=0;
					if(m&&tj+m>K)tk=max(tk,m+1);
					dp2[t+1][tj][tk]=(dp2[t+1][tj][tk]+dp2[t][j][k]*dp[g[a][i]][l][m])%mod;
				}
			}
		}
		t++;
	}
	/*for(int j=0;j<=K+1;j++){
		for(int k=0;k<=K;k++){
			int tj=j;int tk=k;
			if(tj==K+1)tk++;
			dp2[t+1][tj][tk]=(dp2[t+1][tj][tk]+dp2[t][j][k])%mod;
			dp2[t+1][0][0]=(dp2[t+1][0][0]+dp2[t][j][k])%mod;
		}
	}
	t++;*/
	for(int i=0;i<=K+1;i++)for(int j=0;j<=K;j++)dp[a][i][j]=dp2[t][i][j];
//	for(int i=0;i<=K+1;i++)for(int j=0;j<=K;j++){
//		if(dp[a][i][j])printf("%d %d %d: %I64d\n",a,i,j,dp[a][i][j]);
//	}
}
int main(){
	int a,b;scanf("%d%d",&a,&b);
	K=b;
	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);
	}
	calc(0,-1);
	long long ret=0;
	for(int i=0;i<=K+1;i++)ret=(ret+dp[0][i][0])%mod;
	printf("%I64d\n",ret);
}

D:
permutationの個数の偶奇は行列式の偶奇。1要素ずつ取り除いたものを転置してできる行列は余因子行列。余因子行列は、det(A)が奇数なので実質逆行列と同じ。よってビット並列で逆行列を求めるだけ。
プログラミング要素、0。

#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 c[2100][4100];
int s[2100];
int t[2100];
int ans[510000];
typedef unsigned long long wolf;
wolf mat[2100][65];
int D=64;
int x[510000];
int y[510000];
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--;
		c[p][q]=1;
		x[i]=p;y[i]=q;
	}
	for(int i=0;i<a;i++)for(int j=0;j<a*2;j++){
		if(c[i][j]||j==i+a)mat[i][j/D]+=(1LL<<(j%D));
	}
	int cur=0;
	for(int i=0;i<a;i++){
		int at=-1;
		for(int j=cur;j<a;j++){
			if(mat[j][i/D]&(1LL<<(i%D))){
				at=j;break;
			}
		}
		if(!~at)continue;
		for(int k=0;k<65;k++)swap(mat[at][k],mat[cur][k]);
		for(int j=0;j<a;j++){
			if(cur==j)continue;
			if(mat[j][i/D]&(1LL<<(i%D))){
				for(int k=0;k<65;k++)mat[j][k]^=mat[cur][k];
			}
		}

		cur++;
	}
	for(int i=0;i<b;i++){
		if(mat[y[i]][(a+x[i])/D]&(1LL<<((a+x[i])%D)))printf("NO\n");
		else printf("YES\n");
	}
}