ひとり地区予選 2018-2019 ACM-ICPC Southeast USA Regional
これはつまらん(確信)。3時間強の練習会。
B: Count the Bits
5万回見た。ところで間違えてAに提出してWA出した
long long dp[140][140][1100]; int main(){ int a,b;scanf("%d%d",&a,&b); dp[0][0][0]=1; for(int i=0;i<b;i++){ for(int j=0;j<=i;j++){ for(int k=0;k<a;k++){ if(dp[i][j][k]==0)continue; dp[i+1][j][k*2%a]=(dp[i+1][j][k*2%a]+dp[i][j][k])%mod; dp[i+1][j+1][(k*2+1)%a]=(dp[i+1][j+1][(k*2+1)%a]+dp[i][j][k])%mod; } } } long long ret=0; for(int i=0;i<=b;i++){ ret=(ret+i*dp[b][i][0])%mod; } printf("%lld\n",ret); }
C: Exam
無。
char in[2][1100]; int main(){ int a;scanf("%d",&a); scanf("%s%s",in[0],in[1]); int n=strlen(in[0]); int ret=0; for(int i=0;i<n;i++){ if(in[0][i]==in[1][i]&&a){ a--;ret++; } } int cn=0; for(int i=0;i<n;i++){ if(in[0][i]!=in[1][i])cn++; } ret+=cn-a; printf("%d\n",ret); }
F: Knockout
簡単な問題が全く見つからないからうだうだしてたら他の人が解いたので自分もやった
char in[110]; int r[110]; double dp[2][1<<10]; double calc(int a,int b){ if(dp[a][b]>=-0.5)return dp[a][b]; double ret=0; for(int i=2;i<=12;i++){ double p=1.0/36; p*=min(12-i,i-2)+1; double tmp=-1; bool ok=false; int val=0; for(int j=0;j<10;j++){ if(b&(1<<j)){ val*=10;val+=j; } } if(a==0)tmp=val; for(int j=0;j<(1<<10);j++){ if((b&j)!=j)continue; int cur=0; for(int k=0;k<10;k++)if(j&(1<<k))cur+=k; if(cur!=i)continue; ok=true; double tt=calc(a,b-j); if(a==0&&tt<tmp){ tmp=tt; } if(a==1&&tt>tmp){ tmp=tt; } } if(a==1&&ok==false){ tmp=val; } ret+=p*tmp; } // printf("%d %d: %f\n",a,b,ret); return dp[a][b]=ret; } int main(){ scanf("%s",in); int a,b;scanf("%d%d",&a,&b); int n=a+b; int st=0; int v=0; for(int i=0;in[i];i++){ r[in[i]-'0']=1; v*=10; v+=in[i]-'0'; st+=(1<<(in[i]-'0')); } for(int i=0;i<2;i++)for(int j=0;j<(1<<10);j++)dp[i][j]=-1; int mv1=0; double b1=v; int mv2=0; double b2=-1; for(int i=0;i<(1<<10);i++){ if((i&st)!=i)continue; int St=0; for(int j=0;j<10;j++){ if(i&(1<<j))St+=j; } if(St!=n)continue; // printf("%d %d\n",st,i); double tmp1=calc(0,st-i); double tmp2=calc(1,st-i); if(tmp1<b1){ b1=tmp1;mv1=i; } if(tmp2>b2){ b2=tmp2;mv2=i; } } if(mv1==0){ printf("-1"); }else{ for(int i=0;i<10;i++)if(mv1&(1<<i))printf("%d",i); } printf(" %.5f\n",b1); if(mv2==0){ printf("-1"); b2=v; }else{ for(int i=0;i<10;i++)if(mv2&(1<<i))printf("%d",i); } printf(" %.5f\n",b2); }
J: Area Rug
5万回見た。
char in[1100][1100]; int sum[1100][1100]; int ans[11000]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%s",in[i]); for(int i=0;i<a;i++)for(int j=0;j<a;j++){ if(in[i][j]=='D')sum[i+1][j+1]++; } for(int i=0;i<=a;i++)for(int j=0;j<=a;j++){ sum[i+1][j]+=sum[i][j]; } for(int i=0;i<=a;i++)for(int j=0;j<=a;j++){ sum[i][j+1]+=sum[i][j]; } for(int i=0;i<=a-b;i++){ for(int j=0;j<=a-b;j++){ ans[sum[i+b][j+b]-sum[i+b][j]-sum[i][j+b]+sum[i][j]]++; } } for(int i=0;i<=b*b;i++){ if(ans[i]){ printf("%d %d\n",i,ans[i]); } } }
I: Rectangles
Fortune Telling。
int segtree[524288]; int laz[524288]; int z[210000]; pair<pair<int,int>,pair<int,int> > ev[210000]; void update(int a,int b,int c,int d,int e){ if(laz[e]){ laz[e]=0; segtree[e]=(z[b+1]-z[a])-segtree[e]; if(a!=b){ laz[e*2]=!laz[e*2]; laz[e*2+1]=!laz[e*2+1]; } } if(d<a||b<c)return; if(c<=a&&b<=d){ laz[e]=!laz[e]; }else{ update(a,(a+b)/2,c,d,e*2); update((a+b)/2+1,b,c,d,e*2+1); segtree[e]=segtree[e*2]+segtree[e*2+1]; } if(laz[e]){ laz[e]=0; segtree[e]=(z[b+1]-z[a])-segtree[e]; if(a!=b){ laz[e*2]=!laz[e*2]; laz[e*2+1]=!laz[e*2+1]; } } } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ int X1,Y1,X2,Y2; scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2); ev[i*2]=make_pair(make_pair(X1,0),make_pair(Y1,Y2)); ev[i*2+1]=make_pair(make_pair(X2,1),make_pair(Y1,Y2)); z[i*2]=Y1; z[i*2+1]=Y2; } std::sort(z,z+a*2); std::sort(ev,ev+a*2); z[a*2]=mod; long long ret=0; for(int i=0;i<a*2;i++){ int at=ev[i].first.first; int ty=ev[i].first.second; int YL=ev[i].second.first; int YR=ev[i].second.second; int Y1=lower_bound(z,z+a*2,YL)-z; int Y2=lower_bound(z,z+a*2,YR)-z; if(i){ long long ks=ev[i].first.first-ev[i-1].first.first; ret+=ks*segtree[1]; } update(0,262143,Y1,Y2-1,1); } printf("%lld\n",ret); }
K: To Tell the Truth
問題文の意味を推測する。
int L[1100]; int R[1100]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d%d",L+i,R+i); int ret=-1; for(int i=0;i<=a;i++){ int cur=0; for(int j=0;j<a;j++){ if(L[j]<=i&&i<=R[j])cur++; } if(cur==i)ret=i; } printf("%d\n",ret); }
D: Illiteracy
クソゲー(問題文が読みにくくて条件を見落としまくる)。
int bfs[2000000]; char in[2][10]; int t[10]; int v[10]; int main(){ scanf("%s%s",in[0],in[1]); for(int i=0;i<2000000;i++)bfs[i]=-1; int now=0; for(int i=0;i<8;i++){ now*=6; now+=in[0][i]-'A'; } int goal=0; for(int i=0;i<8;i++){ goal*=6; goal+=in[1][i]-'A'; } queue<int>Q; Q.push(now); bfs[now]=0; while(Q.size()){ int at=Q.front(); Q.pop(); int tmp=at; for(int i=7;i>=0;i--){ t[i]=tmp%6;tmp/=6; } for(int i=0;i<8;i++){ if(t[i]==0){ for(int j=0;j<8;j++)v[j]=t[j]; if(i)v[i-1]=(v[i-1]+1)%6; if(i<7)v[i+1]=(v[i+1]+1)%6; }else if(t[i]==1){ for(int j=0;j<8;j++)v[j]=t[j]; if(i&&i<7)v[i+1]=v[i-1]; }else if(t[i]==2){ for(int j=0;j<8;j++)v[j]=t[j]; v[7-i]=(v[7-i]+1)%6; }else if(t[i]==3){ for(int j=0;j<8;j++)v[j]=t[j]; if(i<4){ for(int j=0;j<i;j++)v[j]=(v[j]+1)%6; }else{ for(int j=i+1;j<8;j++)v[j]=(v[j]+1)%6; } }else if(t[i]==4){ for(int j=0;j<8;j++)v[j]=t[j]; if(i&&i<4){ v[0]=(v[0]+1)%6; v[i*2]=(v[i*2]+1)%6; }else if(i>=4&&i<7){ v[7]=(v[7]+1)%6; v[i-(7-i)]=(v[i-(7-i)]+1)%6; } }else{ for(int j=0;j<8;j++)v[j]=t[j]; if(i%2==0){ v[i/2+4]=(v[i/2+4]+1)%6; }else{ v[i/2]=(v[i/2]+1)%6; } } int to=0; for(int j=0;j<8;j++){ to*=6; to+=v[j]; } if(bfs[to]==-1){ bfs[to]=bfs[at]+1; Q.push(to); } } } printf("%d\n",bfs[goal]); }
E: Inversions
(どこかで見たことがあるような気もする)。計算量からしてどうせ凸なので頑張って凸性DPを書く。様々なものをO(1)で求めるために前計算しないといけなくて苦痛。
long long dp[110][210000]; int p[210000]; vector<int>v; int bit[120]; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<120;a|=a+1)bit[a]+=b; } int cnt[110][210000]; long long stf[110][210000]; int cnt2[110][210000]; long long stf2[110][210000]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<a;i++){ if(p[i])v.push_back(p[i]); } long long ret=0; for(int i=0;i<v.size();i++){ ret+=sum(v[i]+1,110); add(v[i],1); } for(int i=0;i<a;i++){ if(p[i]){ cnt[p[i]-1][i]++; } } for(int i=b;i>0;i--)for(int j=0;j<=a;j++){ cnt[i-1][j]+=cnt[i][j]; } for(int i=0;i<=b;i++)for(int j=0;j<=a;j++){ cnt[i][j+1]+=cnt[i][j]; } for(int i=0;i<a;i++){ if(p[i]==0){ stf[0][i+1]++; for(int j=1;j<=b;j++){ stf[j][i+1]=cnt[j][i]; } } } for(int i=0;i<=b;i++){ for(int j=0;j<=a;j++){ stf[i][j+1]+=stf[i][j]; } } // for(int i=0;i<=b;i++){ // for(int j=0;j<=a;j++)printf("%lld ",stf[i][j]);printf("\n"); // } for(int i=0;i<a;i++){ if(p[i]){ cnt2[p[i]+1][i]++; } } for(int i=0;i<=b;i++)for(int j=0;j<=a;j++){ cnt2[i+1][j]+=cnt2[i][j]; } for(int i=0;i<=b;i++)for(int j=a;j>0;j--){ cnt2[i][j-1]+=cnt2[i][j]; } for(int i=0;i<a;i++){ if(p[i]==0){ stf2[0][i+1]++; for(int j=1;j<=b;j++){ stf2[j][i+1]=cnt2[j][i]; } } } for(int i=0;i<=b;i++){ for(int j=0;j<=a;j++){ stf2[i][j+1]+=stf2[i][j]; } } for(int i=0;i<=b+1;i++)for(int j=0;j<=a;j++)dp[i][j]=-inf; dp[b+1][0]=0; vector<int>ind; ind.push_back(0); for(int i=0;i<a;i++)if(p[i]==0)ind.push_back(i+1); for(int i=b;i>=1;i--){ int at=0; for(int j=0;j<=ind.size();j++)dp[i][j]=dp[i+1][j]; for(int j=0;j<ind.size();j++){ long long prev=-1; long long kk=0; while(at<=j){ kk=dp[i+1][at]; long long tmp=kk+(long long)(stf[0][ind[j]]-stf[0][ind[at]])*stf[0][ind[at]]+(stf[i][ind[j]]-stf[i][ind[at]])+(stf2[i][ind[j]]-stf2[i][ind[at]]); if(prev>tmp){ break; } dp[i][j]=max(dp[i][j],tmp);prev=tmp;at++; } at--; // printf("%d %d: %d %lld\n",i,j,at,dp[i][j]); } } long long mm=0; for(int i=1;i<=b+1;i++)for(int j=0;j<=a;j++)mm=max(mm,dp[i][j]); printf("%lld\n",ret+mm); }
公式のGの答えが間違っていたらしい。
