ひとり地区予選 2014-2015 ACM-ICPC Southeast USA Regional
今日もひとりでRegiona練習。ICPC引退したはずなんですけどねぇ...。
E: Hill Number
こういうのはもういいよね。
int dp[20][3][2][10]; char in[20]; int main(){ long long a;scanf("%lld",&a); dp[0][0][0][0]=1; sprintf(in,"%lld",a); int n=0; long long tmp=a; while(tmp){ n++; tmp/=10; } bool ok=false; for(int i=0;i<n;i++){ bool OK=true; for(int j=0;j<n-1;j++){ if(in[j]>in[j+1]&&j<i)OK=false; if(in[j]<in[j+1]&&j>=i)OK=false; } if(OK)ok=true; } if(!ok){ printf("-1\n");return 0; } long long ret=0; for(int i=0;i<n;i++){ for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<10;l++){ if(dp[i][j][k][l]==0)continue; for(int m=0;m<10;m++){ if(i==0&&m==0)continue; int tj=j; if(tj==0){ if(in[i]-'0'>m){ tj=1; } if(in[i]-'0'<m){ tj=2; } } int to=k; if(k==0){ if(m<l)to=1; }else{ if(m>l)to=-1; } if(to==-1)continue; dp[i+1][tj][to][m]+=dp[i][j][k][l]; } } } for(int i=1;i<=n;i++){ for(int j=0;j<3;j++){ if(i==n&&j==2)continue; for(int k=0;k<2;k++)for(int l=0;l<10;l++){ ret+=dp[i][j][k][l]; } } } printf("%lld\n",ret); }
F: Knights
こういうのももういいよね。
int dx[]={1,1,2,2}; int dy[]={-2,2,-1,1}; int t[10][10]; int main(){ int a,b;scanf("%d%d",&a,&b); mat wolf; for(int i=0;i<(1<<(a*2));i++){ for(int j=0;j<(1<<a);j++){ bool ok=true; for(int k=0;k<a*2;k++){ if(i&(1<<k)){ t[k/a][k%a]=1; }else t[k/a][k%a]=0; } for(int k=0;k<a;k++){ if(j&(1<<k)){ t[2][k]=1; }else t[2][k]=0; } for(int k=0;k<2;k++){ for(int l=0;l<a;l++){ if(t[k][l]){ for(int m=0;m<4;m++){ int tr=k+dx[m]; int tc=l+dy[m]; if(tr<3&&tc<a&&tc>=0&&t[tr][tc])ok=false; } } } } if(ok){ wolf.a[(i>>a)+(j<<a)][i]++; } } } mat res=pw(wolf,b); long long ret=0; for(int i=0;i<(1<<(a*2));i++){ ret=(ret+res.a[i][0])%mod; } printf("%lld\n",ret); }
G: Word Ladder
Outputに細かい条件とかタイブレークの仕方とかを大量に並べるのほんまにやめてほしい
char in[1100][10]; int bfs[2][1100]; vector<int>g[1100]; int C[1100][1100]; char out[10]; char tmp[10]; int main(){ int a;scanf("%d",&a); int len=0; for(int i=0;i<a;i++){ scanf("%s",in[i]); } len=strlen(in[0]); for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j)continue; int cnt=0; for(int k=0;k<len;k++){ if(in[i][k]!=in[j][k])cnt++; } C[i][j]=cnt; if(cnt==1){ g[i].push_back(j); } } } if(C[0][1]==0){ printf("0\n0\n"); return 0; } for(int V=0;V<2;V++){ for(int i=0;i<a;i++){ bfs[V][i]=-1; } queue<int>Q; if(V==0){ Q.push(0); bfs[V][0]=0; }else{ Q.push(1); bfs[V][1]=0; } while(Q.size()){ int at=Q.front();Q.pop(); for(int i=0;i<g[at].size();i++){ int to=g[at][i]; if(bfs[V][to]==-1){ bfs[V][to]=bfs[V][at]+1; Q.push(to); } } } } int dist=bfs[0][1]; int ret=mod; for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j)continue; if(C[i][j]!=2)continue; if(bfs[0][i]==-1||bfs[1][j]==-1)continue; int cost=bfs[0][i]+bfs[1][j]+2; if(cost<=ret){ int fi=0; for(int k=0;k<len;k++){ tmp[k]=in[i][k]; if(in[i][k]!=in[j][k]){ if(fi)tmp[k]=in[j][k]; fi++; } } bool tok=true; if(cost==ret){ for(int k=0;k<len;k++){ if(out[k]!=tmp[k]){ if(out[k]>tmp[k])break; if(out[k]<tmp[k]){ tok=false; break; } } } } if(tok){ for(int k=0;k<len;k++)out[k]=tmp[k]; } ret=cost; fi=0; for(int k=0;k<len;k++){ tmp[k]=in[i][k]; if(in[i][k]!=in[j][k]){ if(fi==0)tmp[k]=in[j][k]; fi++; } } tok=true; if(cost==ret){ for(int k=0;k<len;k++){ if(out[k]!=tmp[k]){ if(out[k]>tmp[k])break; if(out[k]<tmp[k]){ tok=false; break; } } } } if(tok){ for(int k=0;k<len;k++)out[k]=tmp[k]; } } } } if(dist==-1&&ret==mod){ printf("0\n-1\n");return 0; } if(dist==-1)dist=mod; if(dist<=ret){ printf("0\n%d\n",dist);return 0; } printf("%s\n%d\n",out,ret); }
C: Containment
まず北米特有の無駄ストーリーのせいで問題文が読めない。虚無。
int main(){ int a;scanf("%d",&a); int S=12*12*12; int T=12*12*12+1; for(int i=0;i<12;i++)for(int j=0;j<12;j++)for(int k=0;k<12;k++){ if(i==0||i==11||j==0||j==11||k==0||k==11){ add_edge(i*144+j*12+k,T,1); } } for(int i=0;i<12;i++)for(int j=0;j<12;j++)for(int k=0;k<11;k++){ add_edge(i*144+j*12+k,i*144+j*12+k+1,1); add_edge(i*144+j*12+k+1,i*144+j*12+k,1); add_edge(i*144+j*1+k*12,i*144+j*1+k*12+12,1); add_edge(i*144+j*1+k*12+12,i*144+j*1+k*12,1); add_edge(i*1+j*12+k*144,i*1+j*12+k*144+144,1); add_edge(i*1+j*12+k*144+144,i*1+j*12+k*144,1); } for(int i=0;i<a;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); x++;y++;z++; add_edge(S,x*144+y*12+z,99999999); } printf("%d\n",max_flow(S,T)); }
H: Shuffles
1回シャッフルすると1~Nを順にたどるのに周回できる回数の最大値が二倍になるんだよね
int p[1100000]; int inv[1100000]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d",p+i);p[i]--; inv[p[i]]=i; } int cnt=0; for(int i=0;i<a-1;i++){ if(inv[i]>inv[i+1])cnt++; } cnt++; int ret=0; int lim=1; while(lim<cnt){ lim*=2;ret++; } printf("%d\n",ret); }
D: Gold Leaf
無能なのでこういうのが一番楽しい
char in[200][200]; int R1,C1,R2,C2; int comp(int a,int b,int c,int d){ if(make_pair(make_pair(R1,C1),make_pair(R2,C2))>make_pair(make_pair(a,b),make_pair(c,d)))return 1; return 0; } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%s",in[i+40]+40); } for(int i=0;i<200;i++)for(int j=0;j<200;j++){ if(in[i][j]=='#')in[i][j]=1; else in[i][j]=0; } R1=C1=R2=C2=mod; for(int i=0;i<a-1;i++){ int r1=i+1; int r2=i+1; int c1=1; int c2=b; if(comp(r1,c1,r2,c2)==0)continue; bool ok=true; for(int k=0;k<a;k++)for(int l=0;l<b;l++){ int tk=k; tk=1+i+(i-k); int tl=l; if(in[k+40][l+40]+in[tk+40][tl+40]!=1)ok=false; } if(ok){ R1=r1;R2=r2;C1=c1;C2=c2; } } for(int i=0;i<b-1;i++){ int c1=i+1; int c2=i+1; int r1=1; int r2=a; if(comp(r1,c1,r2,c2)==0)continue; bool ok=true; for(int k=0;k<a;k++)for(int l=0;l<b;l++){ int tk=k; int tl=l; tl=1+i+(i-l); if(in[k+40][l+40]+in[tk+40][tl+40]!=1)ok=false; } if(ok){ R1=r1;R2=r2;C1=c1;C2=c2; } } for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(i&&j)continue; int r1=i+1; int c1=j+1; int r2=i+1; int c2=j+1; bool ok=true; while(r2<a&&c2<b){ if(in[r2-1+40][c2-1+40]==0)ok=false; r2++;c2++; } if(in[r2-1+40][c2-1+40]==0)ok=false; if(comp(r1,c1,r2,c2)==0)continue; for(int k=0;k<a;k++)for(int l=0;l<b;l++){ if(k-l==i-j)continue; int tk=i+(l-j); int tl=j+(k-i); if(in[k+40][l+40]+in[tk+40][tl+40]!=1)ok=false; } if(ok){ R1=r1;R2=r2;C1=c1;C2=c2; } } for(int i=0;i<a;i++)for(int j=0;j<b;j++){ if(i<a-1&&j)continue; int r1=i+1; int c1=j+1; int r2=i+1; int c2=j+1; bool ok=true; while(r2>1&&c2<b){ if(in[r2-1+40][c2-1+40]==0)ok=false; r2--;c2++; } if(in[r2-1+40][c2-1+40]==0)ok=false; if(comp(r1,c1,r2,c2)==0)continue; // printf("%d %d %d %d\n",r1,c1,r2,c2); for(int k=0;k<a;k++)for(int l=0;l<b;l++){ if(k+l==i+j)continue; int tk=i-(l-j); int tl=j+(i-k); if(in[k+40][l+40]+in[tk+40][tl+40]!=1)ok=false; } if(ok){ R1=r1;R2=r2;C1=c1;C2=c2; } } printf("%d %d %d %d\n",R1,C1,R2,C2); }
B: Stained Carpet
次元を落として比率だと思うのがいいと思う。
inline double dist(double x,double y){return sqrt(x*x+y*y);} int main(){ double A,B,C; scanf("%lf%lf%lf",&A,&B,&C); if(A>B)swap(A,B); if(B>C)swap(B,C); if(A>B)swap(A,B); if(B>C)swap(B,C); // swap(A,C); double left=0; double right=sqrt(3)/2; double left2=0; double right2=1; for(int i=0;i<300;i++){ double M=(left+right)/2; left2=0; right2=1; for(int j=0;j<300;j++){ double M2=(left2+right2)/2; double b=dist(M2,M); double c=dist(1-M2,M); if(b/c<B/C){ left2=M2; }else right2=M2; } double a=dist(left2-0.5,M-sqrt(3)/2); double b=dist(M,left2); if(a/b<A/B){ right=M; }else left=M; } double x=left2; double y=left; //printf("%.12f %.12f %.12f\n",x,y,sqrt(3)/2); if(ABS(x-0.5)-EPS>0.5-y/sqrt(3)){ printf("-1.000\n");return 0; } double th=B/dist(x,y); printf("%f\n",sqrt(3)/4*th*th); }
A,I: Iはどこかで見たことあると思うんだけどなぁ...
今日も自明しか解けなかった、だめですね
