Codeforces Round #366 (Div. 1)
コンテストのバランスを全く考えていない難問セットなのですが、一つ一つはICPCの大変な問題(しかもサンプルも弱い)のような存在で、ただ実装が辛いだけでした。
ちなみにMARVELはヴェノム派です。
| A | B | C | D | E | Place |
|---|---|---|---|---|---|
| 00:16 (+1) | 00:53 (+3) | - | - | - | 33rd |
A:
なんて事はないやるだけ問題なのですが、iとnumを1箇所間違えました。
#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 p[310000]; int at[310000]; vector<int>v[310000]; int main(){ int a,b;scanf("%d%d",&a,&b); int cnt=0; int ind=0; int num=0; for(int i=0;i<b;i++){ int x,y; scanf("%d%d",&x,&y); if(x==1){ cnt++; v[y].push_back(num++); }else if(x==2){ while(at[y]<v[y].size()){ if(!p[v[y][at[y]]])cnt--; p[v[y][at[y]]]=1; at[y]++; } }else{ while(ind<y){ if(!p[ind])cnt--; p[ind]=1; ind++; } } printf("%d\n",cnt); } }
B:
類題はもう何個もあると思います。生きている辺が1本のときの場合分けとかが厄介ですが、サンプルには入っていません。
#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 x[5100]; long long dp[2][10100]; int A[5100]; int B[5100]; int C[5100]; int D[5100]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); b--;c--; for(int i=0;i<a;i++)scanf("%d",x+i); x[a]=mod; for(int i=0;i<a;i++)scanf("%d",A+i); for(int i=0;i<a;i++)scanf("%d",B+i); for(int i=0;i<a;i++)scanf("%d",C+i); for(int i=0;i<a;i++)scanf("%d",D+i); for(int i=0;i<2;i++)for(int j=0;j<10100;j++)dp[i][j]=inf; dp[0][0]=0; for(int i=0;i<a;i++){ int t=i%2; for(int j=0;j<10100;j++)dp[!t][j]=inf; for(int j=0;j<a*2;j++){ if(dp[t][j]==inf)continue; if(i==b){ if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+C[i]); dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+D[i]); }else if(i==c){ if(j>1||(j==1&&i==a-1))dp[!t][j-1]=min(dp[!t][j-1],dp[t][j]+(long long)(j-1)*(x[i+1]-x[i])+A[i]); dp[!t][j+1]=min(dp[!t][j+1],dp[t][j]+(long long)(j+1)*(x[i+1]-x[i])+B[i]); }else{ dp[!t][j+2]=min(dp[!t][j+2],dp[t][j]+(long long)(j+2)*(x[i+1]-x[i])+B[i]+D[i]); if(j>1)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+min(B[i]+C[i],A[i]+D[i])); else if(j==1){ if(b<i)dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+A[i]+D[i]); else dp[!t][j]=min(dp[!t][j],dp[t][j]+(long long)j*(x[i+1]-x[i])+C[i]+B[i]); } if(j>2||(j==2&&i==a-1))dp[!t][j-2]=min(dp[!t][j-2],dp[t][j]+(long long)(j-2)*(x[i+1]-x[i])+A[i]+C[i]); } } } printf("%I64d\n",dp[a%2][0]); }
C:
¬とかを無視すれば輪と直線しかないので、一次元にできてあとはありがちなDPをするだけですが、結構実装量が多いです。
#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 L[110000]; int R[110000]; vector<int>g[110000]; int ABS(int a){ return max(a,-a); } int num=1; int ord[110000]; int lm[110000]; int v[110000]; pair<int,int> p[110000]; long long dp[110000][2][2][2]; vector<int>q[110000]; int main(){ int a,b;scanf("%d%d",&b,&a); for(int i=0;i<b;i++){ int x;scanf("%d",&x); if(x==1){ scanf("%d",L+i); }else{ scanf("%d%d",L+i,R+i); // if(ABS(L[i])<ABS(R[i]))swap(L[i],R[i]); if(ABS(L[i])!=ABS(R[i])){ g[ABS(L[i])].push_back(ABS(R[i])); g[ABS(R[i])].push_back(ABS(L[i])); } } } for(int i=1;i<=a;i++)v[i]=-1; for(int i=1;i<=a;i++)p[i]=make_pair(g[i].size(),i); std::sort(p+1,p+a+1); for(int i=1;i<=a;i++){ int at=p[i].second; if(~v[at])continue; int id=at; int tl=num; if(p[i].first!=2)tl=-1; while(1){ bool ok=false; ord[num]=id; v[id]=num++; lm[id]=tl; for(int j=0;j<g[id].size();j++){ if(~v[g[id][j]])continue; ok=true; id=g[id][j]; break; } if(!ok)break; } } for(int i=0;i<b;i++){ q[max(v[ABS(L[i])],v[ABS(R[i])])].push_back(i); } // for(int i=1;i<=a;i++)printf("%d ",v[i]); // printf("\n"); dp[0][0][0][0]=1; for(int i=0;i<a;i++){ for(int j=0;j<2;j++)for(int k=0;k<2;k++)for(int l=0;l<2;l++){ if(!dp[i][j][k][l])continue; for(int m=0;m<2;m++){ int tl=l; int tk=m; int tj=j; if(lm[ord[i+1]]==i+1)tj=m; for(int t=0;t<q[i+1].size();t++){ int ql=L[q[i+1][t]]; int qr=R[q[i+1][t]]; if(ABS(ql)==ord[i+1]){ if(qr==0){ if(ql>0&&m)tl^=1; if(ql<0&&!m)tl^=1; }else if(ABS(qr)==ord[i+1]){ if(((ql<0)^m)||((qr<0)^m))tl^=1; }else if(ABS(qr)==ord[i]){ if(((ql<0)^m)||((qr<0)^k))tl^=1; }else{ if(((ql<0)^m)||((qr<0)^j))tl^=1; } }else{ if(ABS(ql)==ord[i]){ if(((qr<0)^m)||((ql<0)^k))tl^=1; }else{ if(((qr<0)^m)||((ql<0)^j))tl^=1; } } } dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod; } } } long long ret=0; for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret+=dp[a][i][j][1]; ret%=mod; printf("%d\n",(int)ret); }
