思えば3年前、Good Bye 2013では問題もろくに解けずHackすることだけしてレートを減らしていました。
tozangezan.hatenablog.com
3年後、Codeforcesをやる気になったためついに戻ってきました。
| A | B | C | D | E | F | G | H | Place |
|---|---|---|---|---|---|---|---|---|
| 00:24 | 00:10 | 00:06 | 00:21 | 01:09 | - | - | - | 44th |
Rating: 2510 → 2581 (+71)
残念でした。IGMにはなれませんでした。
A:
これはどうでもいいです。
#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[32]; int vis[410][410]; bool f[410][410][30][8]; int dx[]={1,1,0,-1,-1,-1,0,1}; int dy[]={0,1,1,1,0,-1,-1,-1}; int D=200; int main(){ int a,b;scanf("%d%d",&a,&b); int t=(240-b)/5; for(int i=a;i>=0;i--){ if(i*(i+1)/2<=t){ printf("%d\n",i); return 0; } } }
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; char in[510]; int main(){ int a;scanf("%d",&a); int at=0; while(a--){ int b;scanf("%d%s",&b,in); if(in[0]=='S'){ if(at+b>20000){ printf("NO\n");return 0; } at+=b; }else if(in[0]=='N'){ if(at-b<0){ printf("NO\n");return 0; } at-=b; }else{ if(at==0||at==20000){ printf("NO\n");return 0; } } } if(at==0)printf("YES\n");else printf("NO\n"); }
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 p[210000]; int q[210000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d",p+i,q+i); } int tt=0; for(int i=0;i<a;i++)if(q[i]==2)tt++; if(!tt){ printf("Infinity\n");return 0; } int L=-999999999; int R=999999999; for(int i=0;i<a;i++){ if(q[i]==1){ L=max(L,1900); }else{ R=min(R,1899); } L+=p[i]; R+=p[i]; // printf("%d %d\n",L,R); } if(L>R){ printf("Impossible\n");return 0; } printf("%d\n",R); }
D:
適当にBFSしてください。
#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[32]; int vis[410][410]; bool f[410][410][30][8]; int dx[]={1,1,0,-1,-1,-1,0,1}; int dy[]={0,1,1,1,0,-1,-1,-1}; int D=200; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d",b+i); } b[0]--; queue<pair<pair<int,int>,pair<int,int> > > Q; Q.push(make_pair(make_pair(D,D),make_pair(0,0))); f[D][D][0][0]=1; while(Q.size()){ int row=Q.front().first.first; int col=Q.front().first.second; int ph=Q.front().second.first; int dir=Q.front().second.second;Q.pop(); vis[row][col]=1; for(int i=0;i<b[ph];i++){ row+=dx[dir]; col+=dy[dir]; vis[row][col]=1; } if(ph==a-1)continue; if(!f[row][col][ph+1][(dir+1)%8]){ f[row][col][ph+1][(dir+1)%8]=true; Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+1)%8))); } if(!f[row][col][ph+1][(dir+7)%8]){ f[row][col][ph+1][(dir+7)%8]=true; Q.push(make_pair(make_pair(row,col),make_pair(ph+1,(dir+7)%8))); } } int ret=0; for(int i=0;i<410;i++)for(int j=0;j<410;j++)ret+=vis[i][j]; printf("%d\n",ret); }
E:
AtCoderでも見た、SegtreeにDPの状態i→jのコストをもっておくやつです。もしかしたらこれをライブラリにしておくと強いかも。
#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; char in[210000]; struct wolf{ int t[5][5]; wolf(){for(int i=0;i<5;i++)for(int j=0;j<5;j++)t[i][j]=-1;} }; wolf segtree[524288]; wolf zero; wolf dame; wolf query(int a,int b,int c,int d,int e){ if(d<=a||b<=c)return zero; if(c<=a&&b<=d){ //printf("%d %d %d %d %d\n",a,b,c,d,e); return segtree[e]; } wolf L=query(a,(a+b)/2,c,d,e*2); wolf R=query((a+b)/2,b,c,d,e*2+1); //for(int i=0;i<5;i++){ // for(int j=0;j<5;j++)printf("%d ",R.t[i][j]);printf("\n"); // } wolf ret; for(int i=0;i<5;i++)for(int j=i;j<5;j++){ for(int k=i;k<=j;k++){ //printf("%d %d %d\n",L.t[i][k],R.t[k][j],ret.t[i][j]); if(~L.t[i][k]&&~R.t[k][j]&&(ret.t[i][j]==-1||ret.t[i][j]>L.t[i][k]+R.t[k][j])){ ret.t[i][j]=L.t[i][k]+R.t[k][j]; } } } return ret; } int main(){ int a,b;scanf("%d%d",&a,&b); scanf("%s",in); for(int i=0;i<a;i++){ for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0; if(in[i]=='2'){ segtree[i+262144].t[0][0]=1; segtree[i+262144].t[0][1]=0; }else if(in[i]=='0'){ segtree[i+262144].t[1][1]=1; segtree[i+262144].t[1][2]=0; }else if(in[i]=='1'){ segtree[i+262144].t[2][2]=1; segtree[i+262144].t[2][3]=0; }else if(in[i]=='6'){ segtree[i+262144].t[3][3]=1; segtree[i+262144].t[4][4]=1; }else if(in[i]=='7'){ segtree[i+262144].t[3][3]=1; segtree[i+262144].t[3][4]=0; } } for(int i=a;i<262144;i++)for(int j=0;j<5;j++)segtree[i+262144].t[j][j]=0; for(int i=262143;i>0;i--){ for(int j=0;j<5;j++)for(int k=j;k<5;k++){ for(int l=j;l<=k;l++){ if(segtree[i*2].t[j][l]==-1||segtree[i*2+1].t[l][k]==-1)continue; if(~segtree[i].t[j][k])segtree[i].t[j][k]=min(segtree[i].t[j][k],segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k]); else segtree[i].t[j][k]=segtree[i*2].t[j][l]+segtree[i*2+1].t[l][k]; } } } for(int i=0;i<5;i++)zero.t[i][i]=0; for(int i=0;i<5;i++)for(int j=0;j<5;j++)dame.t[i][j]=-1; while(b--){ int p,q;scanf("%d%d",&p,&q);p--; wolf res=query(0,262144,p,q,1); printf("%d\n",res.t[0][4]); } }
F:
解法は単純なのですが、コードに落とすのが大変です。ICPCの参加権がある人は練習にやってみては？
