CODE FESTIVAL 2014 上海 2日目
あとでAdventarでいろいろします
6位でした。Eでずっと嵌っていたので仕方ない。
A:
まあFA。早解きレーサーの意地。
#include<stdio.h> #include<algorithm> using namespace std; int p10[7]; int main(){ int a; p10[0]=1; for(int i=1;i<7;i++)p10[i]=p10[i-1]*10; scanf("%d",&a); int val=1; for(int i=0;i<a;i++)val*=10; val--; printf("%d\n",val); for(int i=0;i<=val;i++){ for(int j=0;j<a;j++){ if(i/p10[a-j]%2)printf("%d",9-i%p10[a-j]/p10[a-j-1]); else printf("%d",i%p10[a-j]/p10[a-j-1]); } printf("\n"); } }
B:
まあFA。
#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; long long ABS(long long a){return max(a,-a);} int main(){ int a;scanf("%d",&a); while(a--){ long long b;scanf("%lld",&b); b--; long long t=(long long)sqrt((double)b/2); long long n=0; for(int i=-10;i<=10;i++){ if(t+i<0)continue; n=t+i; if(1+(t+i)*(t+i+1)*2>b)break; } long long v=b-(1+(n-1)*(n)*2); long long x=-n+(v+1)/2; long long y=n-ABS(x); if(v%2)y=-y; printf("%lld %lld\n",x,y); } }
C:
regular polygonの意味が分からなくてClarに出るまで解かなかった。それが解決すれば既出というか超典型。
#include<stdio.h> #include<algorithm> #include<set> using namespace std; int x[1100]; int y[1100]; int out[6]; set<pair<int,int> >S; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d%d",x+i,y+i); for(int i=0;i<a;i++)S.insert(make_pair(x[i],y[i])); for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j)continue; int X=x[j]; int Y=y[j]; int dx=x[j]-x[i]; int dy=y[j]-y[i]; X-=dy; Y+=dx; if(!S.count(make_pair(X,Y)))continue; X-=dx; Y-=dy; if(!S.count(make_pair(X,Y)))continue; out[0]=i+1; out[1]=j+1; for(int k=0;k<a;k++){ if(x[k]==x[j]-dy&&y[k]==y[j]+dx)out[2]=k+1; if(x[k]==x[i]-dy&&y[k]==y[i]+dx)out[3]=k+1; } std::sort(out,out+4); printf("4\n"); for(int k=0;k<4;k++)printf("%d\n",out[k]); return 0; } }printf("0\n"); }
D:
フロー復元するだけ。
#include<stdio.h> #include<vector> #include<string.h> #include<queue> #include<algorithm> using namespace std; namespace MCF { } int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; char str[100][100]; int bfs[100][100]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%s",str[i]); for(int i=0;i<100;i++)for(int j=0;j<100;j++)bfs[i][j]=-1; queue<pair<int,int> > Q; int sr,sc; int ar,ac; int br,bc; for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(str[i][j]=='S'){sr=i;sc=j;} if(str[i][j]=='A'){ar=i;ac=j;} if(str[i][j]=='B'){br=i;bc=j;} } Q.push(make_pair(sr,sc)); bfs[sr][sc]=0; while(Q.size()){ int row=Q.front().first; int col=Q.front().second; Q.pop(); for(int i=0;i<4;i++){ if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&!~bfs[row+dx[i]][col+dy[i]]&&str[row+dx[i]][col+dy[i]]!='#'){ bfs[row+dx[i]][col+dy[i]]=bfs[row][col]+1; Q.push(make_pair(row+dx[i],col+dy[i])); } } } int ad=bfs[ar][ac]; int bd=bfs[br][bc]; MCF::init(a*b*2+1); for(int i=0;i<a;i++)for(int j=0;j<b;j++){ MCF::ae(2*(i*b+j),2*(i*b+j)+1,1,0); for(int k=0;k<4;k++){ if(0<=i+dx[k]&&i+dx[k]<a&&0<=j+dy[k]&&j+dy[k]<b&&str[i+dx[k]][j+dy[k]]!='#'){ MCF::ae(2*(i*b+j)+1,2*((i+dx[k])*b+j+dy[k]),1,1); } } } MCF::ae(2*(ar*b+ac)+1,a*b*2,1,0); MCF::ae(2*(br*b+bc)+1,a*b*2,1,0); int res=MCF::solve(2*(sr*b+sc)+1,a*b*2,2); if(!res||MCF::toc>ad+bd){ printf("NA\n");return 0; } int nr=ar; int nc=ac; while(1){ int t=2*(nr*b+nc); int to; for(int i=MCF::ptr[t];~i;i=MCF::next[i]){ if(MCF::col[i]&&MCF::capa[i]){ to=MCF::zu[i]/2; break; } } int tr=to/b; int tc=to%b; if(sr==tr&&sc==tc)break; str[tr][tc]='a'; nr=tr;nc=tc; } nr=br; nc=bc; while(1){ int t=2*(nr*b+nc); int to; for(int i=MCF::ptr[t];~i;i=MCF::next[i]){ if(MCF::col[i]&&MCF::capa[i]){ to=MCF::zu[i]/2; break; } } int tr=to/b; int tc=to%b; if(sr==tr&&sc==tc)break; str[tr][tc]='b'; nr=tr;nc=tc; } for(int i=0;i<a;i++)printf("%s\n",str[i]); }
E:
81は定数みたいなものだから…(Mountain解説参照)
定数倍改善しようとしていて嵌った。結局3^4を消して解決した。
#include<stdio.h> #include<algorithm> using namespace std; double dp[110][110][110][4]; double p[3]; int a,b,c; bool de=false; double solve(int P,int q,int r,int v){ if(dp[P][q][r][v]>-0.5)return dp[P][q][r][v]; if(P==0&&q==0&&r==0)return dp[P][q][r][v]=0; double ret=999999999; for(int i=0;i<3;i++){ int X=P;int Y=q;int Z=r; if(i==0)X--; if(i==1)Y--; if(i==2)Z--; double val=0; double dame=0; if(X<0||Y<0||Z<0){ if(v==0)continue; } if(v==0){ ret=min(ret,(solve(X,Y,Z,v+1)*p[i]+1)/(p[i])); }else if((v==2&&i==0)||v==3){ ret=min(ret,(solve(max(X,0),max(Y,0),max(Z,0),0)*p[i]+solve(P,q,r,0)*(1.0-p[i]))); }else{ ret=min(ret,(solve(max(X,0),max(Y,0),max(Z,0),v+1)*p[i]+solve(P,q,r,0)*(1.0-p[i]))); } } return dp[P][q][r][v]=ret; } int main(){ int d,e,f; scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f); p[0]=0.01*d; p[1]=0.01*e; p[2]=0.01*f; for(int i=0;i<110;i++)for(int j=0;j<110;j++)for(int k=0;k<110;k++) for(int l=0;l<4;l++)dp[i][j][k][l]=-1.0; printf("%.12f\n",solve(a,b,c,0)); }
F:
ほんとこれすき。
累積積をここまでうまく出せるの尊敬する。
頭が悪くて&一度積segtree書いてみたくてsegtree書いてた
#include<stdio.h> #include<algorithm> using namespace std; int s[110000]; int t[110000]; double p[110000]; double q[110000]; double segtree[524288]; void update(int a,double b){ a+=262144; while(a){ segtree[a]*=b; a/=2; } } double query(int a,int b,int c,int d,int e){ if(d<a||b<c)return 1; if(c<=a&&b<=d)return segtree[e]; return query(a,(a+b)/2,c,d,e*2)*query((a+b)/2+1,b,c,d,e*2+1); } pair<int,pair<int,int> >ev[210000]; int S[110000]; int T[110000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d%d",s+i,t+i); ev[i*2]=make_pair(s[i],make_pair(i,0)); ev[i*2+1]=make_pair(t[i],make_pair(i,1)); } std::sort(ev,ev+a*2); for(int i=0;i<524288;i++)segtree[i]=1; for(int i=0;i<a*2;i++){ if(ev[i].second.second==0)S[ev[i].second.first]=i; if(ev[i].second.second==1)T[ev[i].second.first]=i; } int now=0; for(int i=0;i<a*2;i++){ if(ev[i].second.second==0){ now++; }else{ update(i,1.0-1.0/now); now--; } } for(int i=0;i<a;i++){ double P=query(0,262143,S[i],T[i]-1,1); double Q=query(0,262143,S[i],T[i],1); printf("%.12f %.12f\n",1.0-P,Q); } }