AOJ 2383,2442,1325,1326,1327,2426
半日間で気がついたら結構解いていました。
2383
逆辺っぽいものを考えるとどこから来れるか、みたいなものをしゃくとりでもとめていけばかけ算するだけになることがわかります。
#include<stdio.h> #include<algorithm> using namespace std; int v[100000]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d",v+i); std::sort(v,v+a); long long ret=1; int mod=1000000007; int at=0; for(int i=0;i<a;i++){ while(at<a&&v[i]+b>=v[at])at++; // printf("%d\n",at); ret=ret*(at-i)%mod; } printf("%lld\n",ret); }
2442
奇数本だとだめで、偶数本のときは向かい合う辺と同じ長さで平行ならよい。点は座標の平均値。
#include<stdio.h> int x[51]; int y[51]; int main(){ int a; scanf("%d",&a); if(a%2){ printf("NA\n"); return 0; } for(int i=0;i<a;i++){ scanf("%d%d",x+i,y+i); } x[a]=x[0]; y[a]=y[0]; bool ok=true; for(int i=0;i<a/2;i++){ int ax=x[i+1]-x[i]; int ay=y[i+1]-y[i]; int bx=x[i+a/2+1]-x[i+a/2]; int by=y[i+a/2+1]-y[i+a/2]; if(ax+bx||ay+by)ok=false; } if(!ok)printf("NA\n"); else{ double X=0; double Y=0; for(int i=0;i<a;i++){ X+=x[i]; Y+=y[i]; } printf("%f %f\n",X/a,Y/a); } }
1325
問題文の下にあるヒントに従うだけ。
#include<stdio.h> #include<math.h> int gcd(int a,int b){ while(a){ b%=a; int c=a; a=b; b=c; } return b ; } int main(){ int a; scanf("%d",&a); while(a--){ int b,c; scanf("%d%d",&b,&c); int d=b*b+c*c; bool ok=false; for(int i=2;i*i<=d;i++){ if(d%i==0){ for(int k=0;k*k<=i;k++){ int m=(int)(sqrt(i-k*k)+0.0000001); if(m*m+k*k!=i)continue; //printf("%d %d %d\n",m*b+k*c,m*c-k*b,m*m+k*k); if(gcd(m*b+k*c,m*c-k*b)%(m*m+k*k)==0)ok=true; } } } if(ok)printf("C\n"); else printf("P\n"); } }
1326
全探索で余裕。
#include<stdio.h> #include<algorithm> using namespace std; char A[10][100]; char B[10][100]; bool ans[10][800001]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ for(int i=0;i<a;i++)scanf("%s",A[i]); for(int i=0;i<b;i++)scanf("%s",B[i]); for(int i=0;i<b;i++) for(int j=0;j<800001;j++)ans[i][j]=false; for(int i=1;i<=20;i++){ for(int j=1;j<=20;j++){ for(int k=1;k<=20;k++){ bool ok=true; int c=0,d=0,e=0; for(int l=0;l<a;l++){ int in=0; for(int m=0;A[l][m];m++){ if(A[l][m]!='.')break; in++; } if(c*i+d*j+e*k!=in)ok=false; for(int m=0;A[l][m];m++){ if(A[l][m]=='(')c++; if(A[l][m]==')')c--; if(A[l][m]=='{')d++; if(A[l][m]=='}')d--; if(A[l][m]=='[')e++; if(A[l][m]==']')e--; } } if(!ok)continue; c=0; d=0; e=0; for(int l=0;l<b;l++){ ans[l][c*i+d*j+e*k]=true; for(int m=0;B[l][m];m++){ if(B[l][m]=='(')c++; if(B[l][m]==')')c--; if(B[l][m]=='{')d++; if(B[l][m]=='}')d--; if(B[l][m]=='[')e++; if(B[l][m]==']')e--; } } } } } for(int i=0;i<b;i++){ if(i)printf(" "); int at=0; int count=0; for(int j=0;j<800001;j++){ if(ans[i][j]){ at=j; count++; } } if(count>1)printf("-1"); else printf("%d",at); } printf("\n"); } }
1327
行列累乗するだけ。
#include<stdio.h> int mat[50][50]; int val[50][50]; int tmp[50][50]; int v[50]; int main(){ int a,b,c,d,e,f; while(scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f),a){ for(int i=0;i<a;i++)scanf("%d",v+i); for(int i=0;i<a;i++) for(int j=0;j<a;j++) mat[i][j]=val[i][j]=tmp[i][j]=0; for(int i=0;i<a;i++)mat[i][i]=1; for(int i=0;i<a;i++){ if(i)val[i][i-1]=c; val[i][i]=d; if(i<a-1)val[i][i+1]=e; } while(f){ if(f%2){ for(int i=0;i<a;i++) for(int j=0;j<a;j++) tmp[i][j]=0; for(int i=0;i<a;i++) for(int j=0;j<a;j++) for(int k=0;k<a;k++) tmp[i][k]=(tmp[i][k]+mat[i][j]*val[j][k])%b; for(int i=0;i<a;i++) for(int j=0;j<a;j++) mat[i][j]=tmp[i][j]; } f/=2; for(int i=0;i<a;i++) for(int j=0;j<a;j++) tmp[i][j]=0LL; for(int i=0;i<a;i++) for(int j=0;j<a;j++) for(int k=0;k<a;k++) tmp[i][k]=(tmp[i][k]+val[i][j]*val[j][k])%b; for(int i=0;i<a;i++) for(int j=0;j<a;j++) val[i][j]=tmp[i][j]; } for(int i=0;i<a;i++){ if(i)printf(" "); int ret=0; for(int j=0;j<a;j++)ret=(ret+mat[i][j]*v[j])%b; printf("%d",ret); } printf("\n"); } }
2426
座標圧縮+累積和
#include<stdio.h> #include<algorithm> using namespace std; int sum[5002][5002]; int x[5002]; int y[5002]; int X[5002]; int Y[5002]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d%d",x+i,y+i); X[i]=x[i]; Y[i]=y[i]; } X[a]=-1999999999; X[a+1]=1999999999; Y[a]=-1999999999; Y[a+1]=1999999999; std::sort(X,X+a+2); std::sort(Y,Y+a+2); for(int i=0;i<a;i++){ x[i]=lower_bound(X,X+a+2,x[i])-X; y[i]=lower_bound(Y,Y+a+2,y[i])-Y; sum[x[i]][y[i]]++; } for(int i=0;i<a+2;i++){ for(int j=1;j<a+2;j++){ sum[i][j]+=sum[i][j-1]; } } for(int i=0;i<a+2;i++){ for(int j=1;j<a+2;j++){ sum[j][i]+=sum[j-1][i]; } } for(int i=0;i<b;i++){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); int P=lower_bound(X,X+a+2,p)-X-1; int Q=lower_bound(Y,Y+a+2,q)-Y-1; int R=upper_bound(X,X+a+2,r)-X-1; int S=upper_bound(Y,Y+a+2,s)-Y-1; printf("%d\n",sum[R][S]-sum[R][Q]-sum[P][S]+sum[P][Q]); } }
うーん何かこの練習、実装力しかあがってない気がするなあ