結果もあれだがひどいセット。
| 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"); } }
