tozangezan's diary

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

ひとり地区予選 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はどこかで見たことあると思うんだけどなぁ...

今日も自明しか解けなかった、だめですね