tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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]);
    }
}

うーん何かこの練習、実装力しかあがってない気がするなあ