ひとり地区予選 2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)
3時間。クッキーチームには勝てなかったけど、一人でこれだけできれば上出来。
A: Alphabet
リス。
char in[52]; int dp[60]; int main(){ scanf("%s",in); int n=strlen(in); for(int i=0;i<n;i++){ dp[i]=max(dp[i],1); for(int j=0;j<i;j++){ if(in[j]<in[i])dp[i]=max(dp[i],dp[j]+1); } } int ret=0; for(int i=0;i<n;i++)ret=max(ret,dp[i]); printf("%d\n",26-ret); }
C: Cameras
狼はGreedyをBITでごまかす。
int bit[110000]; 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<110000;a|=(a+1))bit[a]+=b; } int main(){ int a,b,c;scanf("%d%d%d",&a,&b,&c); for(int i=0;i<b;i++){ int p;scanf("%d",&p);p--; add(p,1); } int ret=0; for(int i=c-1;i<a;i++){ if(sum(i-c+1,i)<2){ if(sum(i,i)){ ret++;add(i-1,1); }else{ ret++;add(i,1); if(sum(i-c+1,i)==1){ ret++;add(i-1,1); } } } } printf("%d\n",ret); }
F: Illumination
2-SAT.
vector<int>g[5100]; vector<int>rev[5100]; int v[5100]; // used twice int num[5100]; // inverse of conv int conv[5100]; // dfs order of i-th vertex. note that it's kaerigake ordered int scc[5100]; // the index of scc containing i-th vertex int fi[5100]; // the first element of each scc int ss[5100]; // size of each scc int cur; void dfs(int a){ for(int i=0;i<g[a].size();i++){ if(v[g[a][i]])continue; v[g[a][i]]=1; dfs(g[a][i]); } conv[a]=cur; num[cur++]=a; } void dfs2(int a){ scc[a]=cur; ss[cur]++; for(int i=0;i<rev[a].size();i++){ if(v[rev[a][i]])continue; v[rev[a][i]]=1; dfs2(rev[a][i]); } } int x[1100]; int y[1100]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ scanf("%d%d",x+i,y+i); } for(int i=0;i<c;i++){ for(int j=i+1;j<c;j++){ if(x[i]==x[j]){ if(ABS(y[i]-y[j])<=2*b){ g[i*2].push_back(j*2+1); g[j*2].push_back(i*2+1); rev[i*2+1].push_back(j*2); rev[j*2+1].push_back(i*2); } } if(y[i]==y[j]){ if(ABS(x[i]-x[j])<=2*b){ g[i*2+1].push_back(j*2); g[j*2+1].push_back(i*2); rev[i*2].push_back(j*2+1); rev[j*2].push_back(i*2+1); } } } } for(int i=0;i<2*c;i++){ if(v[i])continue; v[i]=1; dfs(i); } cur=0; for(int i=0;i<c*2;i++)v[i]=0; for(int i=c*2-1;i>=0;i--){ if(v[num[i]])continue; v[num[i]]=1; fi[cur]=num[i]; dfs2(num[i]); cur++; } for(int i=0;i<c;i++){ if(scc[i*2]==scc[i*2+1]){ printf("NO\n");return 0; } } printf("YES\n"); }
H: Paint
区間のことも頂点だと思う。
long long dp1[410000]; long long dp2[210000]; vector<pair<pair<long long,int> ,int> > ev; int main(){ long long a; int n;scanf("%I64d%d",&a,&n); for(int i=0;i<n;i++){ long long p,q;scanf("%I64d%I64d",&p,&q); p--; ev.push_back(make_pair(make_pair(p,1),i)); ev.push_back(make_pair(make_pair(q,0),i)); } std::sort(ev.begin(),ev.end()); for(int i=0;i<210000;i++)dp2[i]=inf; for(int i=0;i<410000;i++)dp1[i]=inf; long long now=0; long long cur=0; for(int i=0;i<ev.size();i++){ int at=ev[i].second; long long ad=ev[i].first.first-now; now+=ad;cur+=ad; if(ev[i].first.second==1){ dp2[at]=min(dp2[at],cur); }else{ if(cur>dp2[at]){ cur=dp2[at]; } } } cur+=a-now; printf("%I64d\n",cur); }
K: Tournament Wins
算数。
int main(){ int a,b;scanf("%d%d",&a,&b); double ret=0; int rem=(1<<a)-b; int n=(1<<a); for(int i=0;i<a;i++){ double ks=1; int t=(1<<(i+1))-1; if(t>rem){ break; } for(int j=0;j<t;j++){ ks*=(double)(rem-j)/(n-1-j); } ret+=ks; } printf("%.5f\n",ret); }
I: Postman
Greedy.
pair<int,int>p[1100]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ int s,t;scanf("%d%d",&s,&t); p[i]=make_pair(s,t); }std::sort(p,p+a); long long ret=0; int tmp=b; for(int i=0;i<a;i++){ if(p[i].first>=0)break; if(tmp+p[i].second<=b){ tmp+=p[i].second;continue; } int req=p[i].second; req-=b-tmp; int sk=req/b; ret+=(long long)(-p[i].first)*sk; req-=sk*b; if(req){ tmp=req; ret+=(-p[i].first); }else{ tmp=b; } } tmp=b; for(int i=a-1;i>=0;i--){ if(p[i].first<=0)break; if(tmp+p[i].second<=b){ tmp+=p[i].second;continue; } int req=p[i].second; req-=b-tmp; int sk=req/b; ret+=(long long)(p[i].first)*sk; req-=sk*b; if(req){ tmp=req; ret+=(p[i].first); }else{ tmp=b; } } printf("%I64d\n",ret*2); }
B: Buggy Robot
がんばる
int bfs[60][60][60]; int dx[]={-1,1,0,0}; int dy[]={0,0,-1,1}; char dir[6]="UDLR"; char in[60][60]; char str[60]; int v[60][60][60]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%s",in[i]); } scanf("%s",str); int n=strlen(str); int sx,sy,gx,gy; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(in[i][j]=='R'){ sx=i;sy=j; } if(in[i][j]=='E'){ gx=i;gy=j; } } for(int i=0;i<a;i++)for(int j=0;j<b;j++)for(int k=0;k<=n;k++){ bfs[i][j][k]=-1; } bfs[sx][sy][0]=0; deque<pair<pair<int,int>,int> >Q; Q.push_back(make_pair(make_pair(sx,sy),0)); while(Q.size()){ int row=Q.front().first.first; int col=Q.front().first.second; int at=Q.front().second;Q.pop_front(); if(v[row][col][at])continue; v[row][col][at]=1; if(at<n){ int tr=row; int tc=col; for(int i=0;i<4;i++)if(dir[i]==str[at]){ tr+=dx[i];tc+=dy[i]; } if(tr<0||tr>=a||tc<0||tc>=b||in[tr][tc]=='#'){ tr=row;tc=col; } if(bfs[tr][tc][at+1]==-1||bfs[tr][tc][at+1]>bfs[row][col][at]){ bfs[tr][tc][at+1]=bfs[row][col][at]; Q.push_front(make_pair(make_pair(tr,tc),at+1)); } } for(int i=0;i<4;i++){ int tr=row+dx[i]; int tc=col+dy[i]; if(tr<0||tr>=a||tc<0||tc>=b||in[tr][tc]=='#'){ tr=row;tc=col; } if(bfs[tr][tc][at]==-1){ bfs[tr][tc][at]=bfs[row][col][at]+1; Q.push_back(make_pair(make_pair(tr,tc),at)); } } } int ret=mod; for(int i=0;i<=n;i++)ret=min(ret,bfs[gx][gy][i]); printf("%d\n",ret); }
J: Shopping
modで半分になるやつを Sparse Table で高速化。
long long p[210000]; long long st[20][262144]; int fnd(int a,long long b){ int ret=a; for(int i=19;i>=0;i--){ if(st[i][ret]>b){ ret+=(1<<i); } if(ret>=262144)break; } return ret; } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%I64d",p+i); } for(int i=0;i<262144;i++){ for(int j=0;j<20;j++)st[j][i]=inf; } for(int i=0;i<a;i++){ st[0][i]=p[i]; } for(int i=1;i<20;i++){ for(int j=0;j<262144;j++){ st[i][j]=min(st[i-1][j],j+(1<<(i-1))<262144?st[i-1][j+(1<<(i-1))]:inf); } } while(b--){ long long v; int l,r; scanf("%I64d%d%d",&v,&l,&r); l--; int at=l; while(at<r){ int to=fnd(at,v); if(to>=r){ break; } v%=p[to]; at=to; } printf("%I64d\n",v); } }
L: Windy Path
絶対できる。次に正しく曲がるために一番角度がきついものを選ぶ。
Pt p[60]; int v[60]; char in[60]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ int X,Y;scanf("%d%d",&X,&Y); p[i]=Pt(X,Y)*Pt(cos(1),sin(1)); } int st=0; for(int i=0;i<a;i++){ if(p[i].x<p[st].x)st=i; } scanf("%s",in); printf("%d",st+1); v[st]=1; for(int i=0;i<a-1;i++){ int to=0; if(in[i]=='R')to=1; int nx=0; for(int j=0;j<a;j++)if(!v[j])nx=j; if(to){ // 一番左を選ぶ for(int j=0;j<a;j++){ if(v[j])continue; if(iSP(p[st],p[nx],p[j])==1)nx=j; } }else{ // 一番右を選ぶ for(int j=0;j<a;j++){ if(v[j])continue; if(iSP(p[st],p[nx],p[j])==-1)nx=j; } } st=nx; v[st]=1; printf(" %d",st+1); } printf("\n"); }
G: Maximum Islands
すでにある陸の周りを海で塗って残りはフロー。LとWを間違えた(は？)。
int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; char in[50][50]; const int D_MAX_V=5002; const int D_v_size=5002; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } int UF[2000]; int FIND(int a){ if(UF[a]<0)return a;return UF[a]=FIND(UF[a]); } void UNION(int a,int b){ a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a; } 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*b;i++)UF[i]=-1; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(in[i][j]=='L'){ for(int k=0;k<4;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=a||tc>=b)continue; if(in[tr][tc]=='C')in[tr][tc]='W'; if(in[tr][tc]=='L'){ UNION(i*b+j,tr*b+tc); } } } } int ret=0; for(int i=0;i<a;i++){ for(int j=0;j<b;j++){ if(in[i][j]=='L'&&FIND(i*b+j)==(i*b+j))ret++; } } int S=a*b; int T=a*b+1; int cnt=0; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(in[i][j]=='C'){ cnt++; if((i+j)%2){ add_edge(S,i*b+j,1); for(int k=0;k<4;k++){ int tr=i+dx[k]; int tc=j+dy[k]; if(tr<0||tc<0||tr>=a||tc>=b)continue; if(in[tr][tc]=='C'){ add_edge(i*b+j,tr*b+tc,1); } } }else{ add_edge(i*b+j,T,1); } } } ret+=cnt-max_flow(S,T); printf("%d\n",ret); }
D: Contest Strategy
ひさしぶりに非やるだけを解いた。
t番目の要素ごとに独立で、それぞれに対して dp[i][j][k]: i番目まで見てt番目より大きいものがj回出てきた、すでにt番目が出現したかどうか、を持てばよい。t番目を解くのは、jがK-1以上かつkが1になった最初のタイミング。
long long dp[310][310][2]; int p[310]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d",p+i); } std::sort(p,p+a); long long ret=0; for(int i=0;i<a;i++){ long long ks; if(a-i<b){ ks=(a-i)*p[i]; for(int j=1;j<=a;j++)ks=ks*j%mod; //printf("%lld\n",ks); ret=(ret+ks)%mod; continue; } ks=0; for(int j=0;j<=a;j++)for(int k=0;k<=a;k++)for(int l=0;l<2;l++) dp[j][k][l]=0; dp[0][0][0]=1; for(int j=0;j<a;j++){ for(int k=0;k<a;k++){ for(int l=0;l<2;l++){ if(!dp[j][k][l])continue; // printf("%d %d %d %d: %lld\n",i,j,k,l,dp[j][k][l]); if(l==0){ dp[j+1][k][1]=(dp[j+1][k][1]+dp[j][k][l])%mod; if((a-1-i-k)>0)dp[j+1][k+1][0]=(dp[j+1][k+1][0]+dp[j][k][l]*(a-1-i-k))%mod; if(i+k-j>0)dp[j+1][k][0]=(dp[j+1][k][0]+dp[j][k][l]*(i+k-j))%mod; }else{ if(k>=b-1)continue; if((a-1-i-k)>0)dp[j+1][k+1][1]=(dp[j+1][k+1][1]+dp[j][k][l]*(a-1-i-k))%mod; if(i+k-j+1>0)dp[j+1][k][1]=(dp[j+1][k][1]+dp[j][k][l]*(i+k-j+1))%mod; } } } } long long t=1; for(int j=a;j>=b;j--){ for(int k=b-1;k<=a;k++){ ks=(ks+dp[j][k][1]*(a-j+b)%mod*t)%mod; } t=t*(a-j+1)%mod; } ret=(ret+ks*p[i])%mod; // printf("%lld\n",ks*p[i]%mod); } printf("%lld\n",ret); }
E: Enclosure
絶対やばいと思うんですが...
