Codeforces Round #380 (Div. 1, Rated, Based on Technocup 2017 - Elimination Round 2)
なぜに6問...充実しすぎて2時間でやるなら5問でも十分だと思えるセット。
| A | B | C | D | E | F | Place |
|---|---|---|---|---|---|---|
| 00:19 | 00:28 | 00:37 | 01:49 (+2) | - | - | 34th |
A:
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; pair<int,int> p[210000]; int f[210000]; int g[210000]; int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); int ret=mod; for(int i=0;i<a;i++){ int x,y; scanf("%d%d",&x,&y); p[i]=make_pair(y,x); } std::sort(p,p+a); for(int i=0;i<b;i++)scanf("%d",f+i); f[b]=c; std::sort(f,f+b+2); for(int i=0;i<b+1;i++){ g[i]=f[i+1]-f[i]; } std::sort(g,g+b+1); b++; int at=0; long long tn=0; long long al=0; for(int i=0;i<b;i++)tn+=g[i]; tn*=3; for(int i=0;i<a;i++){ if(g[b-1]>p[i].first)continue; while(at<b&&g[at]*2<=p[i].first){ tn-=3LL*g[at]; al+=g[at]; at++; } long long cost=al+tn-(long long)(b-at)*p[i].first; //printf("%d: %d %I64d %d %d\n",i,at,tn,al,cost); if(cost<=d)ret=min(ret,p[i].second); } if(ret==mod)ret=-1; printf("%d\n",ret); }
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[210000]; int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); scanf("%s",in); int rem=0; int ren=0; for(int i=0;i<a;i++){ if(in[i]=='0'){ ren++; }else{ rem+=ren/c; ren=0; } } rem+=ren/c; vector<int>ret; ren=0; for(int i=0;i<a;i++){ if(rem<b)break; if(in[i]=='0'){ ren++; if(ren%c==0){ ret.push_back(i+1); rem--; } }else{ ren=0; } } printf("%d\n",(int)(ret.size())); for(int i=0;i<ret.size();i++){ if(i)printf(" "); printf("%d",ret[i]); }printf("\n"); }
C:
nがあるなら1~n-1が全部揃っているので、nを全部試す。他所に0があるとか0のあるべきところに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[210000]; int d[210000]; int z[210000]; int sum[210000]; int main(){ int a,b;scanf("%d%d",&a,&b);b--; if(a==1){ printf("0\n");return 0; } for(int i=0;i<a;i++)scanf("%d",c+i); int ba=0; int f=0; for(int i=0;i<a;i++){ if(b==i&&c[i]){ ba++; }else if(b!=i&&c[i]==0){ //ba++; f++; }else{ d[c[i]]++; } } int ret=88888888; for(int i=1;i<a;i++){ z[i]=z[i-1]; if(!d[i])z[i]++; } for(int i=a-1;i>0;i--){ sum[i]=sum[i+1]+d[i]; } for(int i=1;i<a;i++){ int t=f+sum[i+1]; int tot=max(t,z[i]); ret=min(ret,ba+tot); } printf("%d\n",ret); }
D:
実は状態数が少ない(取ったカードの枚数の差がk以下、kもO(N^0.5))ので普通に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 b[4100]; int sum[4100]; int dp[4100][200][100]; int K=95; int ABS(int a){ return max(a,-a); } int N; int calc(int a,int b,int c){ //if(a<0||b+K<0||c<0)printf("dame\n"); ///if(a>=4100||b+K>=200||c>=100)printf("dame\n"); if(dp[a][b+K][c]!=-mod)return dp[a][b+K][c]; int s=a;int t=a+b; int L=a; int R=N-a-b; if(R-L<c){ return dp[s][t-s+K][c]=0; } int ret=-mod; if(s<=t){ if(L+c+1<=R){ ret=max(ret,-calc(s+c+1,t-(s+c+1),c+1)+sum[L+c+1]-sum[L]); } ret=max(ret,-calc(s+c,t-s-c,c)+sum[L+c]-sum[L]); }else{ if(L+c+1<=R){ ret=max(ret,-calc(s,t+c+1-s,c+1)+sum[R]-sum[R-c-1]); } ret=max(ret,-calc(s,t+c-s,c)+sum[R]-sum[R-c]); } //if(s<0||t-s+K<0||c<0)printf("%d %d %d: %d\n",s,t-s+K,c,ret); return dp[s][t-s+K][c]=ret; } int main(){ int a;scanf("%d",&a); N=a; for(int i=0;i<a;i++)scanf("%d",b+i); for(int i=0;i<a;i++)sum[i+1]=sum[i]+b[i]; for(int i=0;i<4100;i++)for(int j=0;j<200;j++)for(int k=0;k<100;k++) dp[i][j][k]=-mod; printf("%d\n",calc(0,0,1)); }
E:
フローでできることの範疇を超えている気がする。また今度。
