読者です 読者をやめる 読者になる 読者になる

AOJ 2372,2361,2356,2386,2241,1250,1181,2340,2243,2232,2175,1316

4日間で気がついたら結構解いていました。

2372
紙に書いて法則を発見するとか。フィボナッチ数列で行列累乗もするし、いろいろと面倒な問題。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long mat[2][2];
long long now[2][2];
long long tmp[2][2];
int mod=1000000007;
long long fib(long long a){
    now[0][0]=now[1][0]=now[0][1]=1;
    now[1][1]=0;
    mat[0][0]=mat[1][1]=1;
    mat[0][1]=mat[1][0]=0;
    while(a){
        if(a%2){
            tmp[0][0]=now[0][0]*mat[0][0]+now[0][1]*mat[1][0];
            tmp[0][1]=now[0][0]*mat[0][1]+now[0][1]*mat[1][1];
            tmp[1][0]=now[1][0]*mat[0][0]+now[1][1]*mat[1][0];
            tmp[1][1]=now[1][0]*mat[0][1]+now[1][1]*mat[1][1];
            mat[0][0]=tmp[0][0]%mod;mat[0][1]=tmp[0][1]%mod;mat[1][0]=tmp[1][0]%mod;mat[1][1]=tmp[1][1]%mod;
        }
        tmp[0][0]=now[0][0]*now[0][0]+now[0][1]*now[1][0];
        tmp[0][1]=now[0][0]*now[0][1]+now[0][1]*now[1][1];
        tmp[1][0]=now[1][0]*now[0][0]+now[1][1]*now[1][0];
        tmp[1][1]=now[1][0]*now[0][1]+now[1][1]*now[1][1];
        now[0][0]=tmp[0][0]%mod;now[0][1]=tmp[0][1]%mod;now[1][0]=tmp[1][0]%mod;now[1][1]=tmp[1][1]%mod;
        a/=2;
    }
    //printf("%lld\n",mat[0][0]);
    return mat[0][0];
}
int main(){
    long long a;
    scanf("%lld",&a);
    long long left=0;
    long long right=2100000000LL;
    while(left+1<right){
        long long M=(left+right)/2;
        long long t=(M-1)/2*((M-1)/2+1);
        if(M%2==0)t+=M/2;
        //printf("%lld %lld\n",M,t);
        if(t>=a){
            right=M;
        }else{
            left=M;
        }
    }
    long long t=(left-1)/2*((left-1)/2+1);
    if(left%2==0)t+=left/2;
    long long v=a-t;
    //printf("%lld %lld\n",left,v);
    if(v<=(right/2+1)/2){
        long long p=v*2-1;
        long long q=right-p;
    //  printf("%lld %lld\n",p,q);
        printf("%d\n",fib(p)*fib(q)%mod);
    }else{
        long long p=(right/2-v+1)*2;
        long long q=right-p;
    //  printf("%lld %lld\n",p,q);
        printf("%d\n",fib(p)*fib(q)%mod);
    }
}

2361
8!頂点でDijkstraしても十分間に合う。

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
int c[8][8];
struct wolf{
    int v[8];
};
inline bool operator<(const wolf&a,const wolf&b){
    for(int i=0;i<8;i++)if(a.v[i]!=b.v[i])return a.v[i]<b.v[i];
    return false;
}
map<wolf,int>ijk;
priority_queue<pair<int,wolf> > Q;
int main(){
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            scanf("%d",&c[i][j]);
    wolf s;
    for(int i=0;i<a;i++)s.v[i]=i;
    Q.push(make_pair(0,s));
    int ret=0;
    while(Q.size()){
        int cost=-Q.top().first;
        wolf now=Q.top().second;
        Q.pop();
        if(ijk.count(now))continue;
        ijk[now]=cost;
        ret=max(ret,cost);
        for(int i=0;i<a;i++)
            for(int j=i+1;j<a;j++){
                int w=now.v[i];
                now.v[i]=now.v[j];
                now.v[j]=w;
                if(!ijk.count(now)){
                    Q.push(make_pair(-cost-c[i][j],now));
                }
                w=now.v[i];
                now.v[i]=now.v[j];
                now.v[j]=w;
            }
    }
    printf("%d\n",ret);
     
}

2356
左右対称なので半分だけ見る。まず奇数回使われる文字が2つ以上あったら作れない。他の場合は2で割ってから組み合わせ計算。

#include<stdio.h>
int d[26];
char str[42];
int main(){
    scanf("%s",str);
    for(int i=0;str[i];i++)d[str[i]-'a']++;
    int v=0;
    for(int i=0;i<26;i++)if(d[i]%2)v++;
    if(v>1)printf("0\n");
    else{
        int n=0;
        for(int i=0;i<26;i++){
            d[i]/=2;
            n+=d[i];
        }
        long long ret=1;
        for(int i=0;i<n;i++)ret*=i+1;
        for(int i=0;i<26;i++){
            //long long val=1;
            for(int j=1;j<=d[i];j++)ret/=j;
        }
        printf("%lld\n",ret);
    }
}

2386
実は、完全グラフなら向きをどのように限定してもハミルトン閉路があります(未証明)

#include<stdio.h>
#include<algorithm>
using namespace std;
int d[1000][1000];
int main(){
    int a;
    scanf("%d",&a);
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++)
            scanf("%d",&d[i][j]);
    long long ret=0;
    for(int i=0;i<a;i++)
        for(int j=i+1;j<a;j++)
            ret+=min(d[i][j],d[j][i]);
    printf("%lld\n",ret);
}

2241
シミュレーションをするだけ。n=1に注意。

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int> unagi[1000000];
pair<int,int> wolf[1000000];
int u_row[500];
int u_col[500];
int w_row[500];
int w_col[500];
int main(){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    for(int i=0;i<1000000;i++){
        unagi[i]=make_pair(-1,-1);
        wolf[i]=make_pair(-1,-1);
    }
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++){
            int p;
            scanf("%d",&p);
            unagi[p-1]=make_pair(i,j);
        }
    for(int i=0;i<a;i++)
        for(int j=0;j<a;j++){
            int p;
            scanf("%d",&p);
            wolf[p-1]=make_pair(i,j);
        }
    int UL=0;
    int UR=0;
    int WL=0;
    int WR=0;
    int u=0;int w=0;
    if(a==1){
        for(int i=0;i<d;i++){
            int e;
            scanf("%d",&e);e--;
            if(~unagi[e].first)u++;
            if(~wolf[e].first)w++;
        if(u>=b&&w>=c){
            printf("DRAW\n");
            return 0;
        }
        if(u>=b){
            printf("USAGI\n");
            return 0;
        }
        if(w>=c){
            printf("NEKO\n");
            return 0;
        }
        }
        printf("DRAW\n");
        return 0;
    }
    for(int i=0;i<d;i++){
        int e;
        scanf("%d",&e);e--;
        if(~unagi[e].first){
            u_row[unagi[e].first]++;
            if(u_row[unagi[e].first]==a)u++;
            u_col[unagi[e].second]++;
            if(u_col[unagi[e].second]==a)u++;
            if(unagi[e].first==unagi[e].second){
                UL++;
                if(UL==a)u++;
            }
            if(unagi[e].first+unagi[e].second==a-1){
                UR++;
                if(UR==a)u++;
            }
        }
        if(~wolf[e].first){
            w_row[wolf[e].first]++;
            if(w_row[wolf[e].first]==a)w++;
            w_col[wolf[e].second]++;
            if(w_col[wolf[e].second]==a)w++;
            if(wolf[e].first==wolf[e].second){
                WL++;
                if(WL==a)w++;
            }
            if(wolf[e].first+wolf[e].second==a-1){
                WR++;
                if(WR==a)w++;
            }
        }
        if(u>=b&&w>=c){
            printf("DRAW\n");
            return 0;
        }
        if(u>=b){
            printf("USAGI\n");
            return 0;
        }
        if(w>=c){
            printf("NEKO\n");
            return 0;
        }
    }
    printf("DRAW\n");
}

1250
下位ビットから決めていく。繰り上がりとかが面倒なのでこれは別の変数にもっておくとよい。

#include<stdio.h>
#include<algorithm>
typedef unsigned int wolf;
char set[]="0123456789abcdef";
wolf b[9];
char str[9];
char out[9];
int main(){
    int a;
    scanf("%d",&a);
    while(a--){
        for(int i=0;i<9;i++)b[i]=0;
        for(int i=0;i<9;i++){
            scanf("%s",str);
            for(int j=0;str[j];j++){
                b[i]*=16;
                for(int k=0;k<16;k++)if(set[k]==str[j])b[i]+=k;
            }
        }
        wolf ans=0;
        //int c=0;
        int d=0;
        for(int i=0;i<32;i++){
            int c=0;
            //int d=0;
            for(int j=0;j<8;j++){
                if(b[j]&(1<<i))c++;
            }
            int e=0;
            if(b[8]&(1<<i))e++;
            if((c+d+e)%2){
                ans+=(1<<i);
                d=(8-c+d)/2;
            }
            else d=(c+d)/2;
        }
        int now=0;
        if(ans==0){
            printf("0\n");
            continue;
        }
        while(ans){
            out[now++]=set[ans%16];
            ans/=16;
        }
        for(int i=now-1;i>=0;i--)printf("%c",out[i]);
        printf("\n");
    }
}

1181
シミュレーションするだけ。ポインタ分かりません(大嘘)

#include<stdio.h>
#include<algorithm>
using namespace std;
int h[100][100];
int t[100][100];
int c[6][4]={{4,2,3,5},{1,3,6,4},{5,6,2,1},{6,2,1,5},{3,6,4,1},{5,4,2,3}};
int d[6][4]={{5,4,2,3},{3,6,4,1},{6,2,1,5},{5,6,2,1},{1,3,6,4},{4,2,3,5}};
struct dice{
    int U,D,F,B,L,R;
    dice(int a,int b){
        U=a;
        F=b;
        D=7-a;
        B=7-b;
        for(int i=0;i<6;i++)
            for(int j=0;j<4;j++)if(a==c[i][j]&&b==d[i][j])L=i+1;
        R=7-L;
    }
};
 
void N(dice &a){
    int q=a.U;a.U=a.F;a.F=a.D;a.D=a.B;a.B=q;
}
void E(dice &a){
    int q=a.U;a.U=a.L;a.L=a.D;a.D=a.R;a.R=q;
}
void W(dice &a){
    int q=a.U;a.U=a.R;a.R=a.D;a.D=a.L;a.L=q;
}
void S(dice &a){
    int q=a.U;a.U=a.B;a.B=a.D;a.D=a.F;a.F=q;
}
int main(){
    int a;
    while(scanf("%d",&a),a){
        for(int i=0;i<100;i++)
            for(int j=0;j<100;j++)
                h[i][j]=t[i][j]=0;
        for(int i=0;i<a;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            dice s=dice(x,y);
            int row=50;
            int col=50;
            bool ok=false;
            do{
                ok=false;
                for(int j=6;j>=4&&!ok;j--){
                    if(h[row][col]>h[row-1][col]&&s.B==j){
                        row--;
                        N(s);
                        ok=true;
                    }else if(h[row][col]>h[row+1][col]&&s.F==j){
                        row++;
                        S(s);ok=true;
                    }else if(h[row][col]>h[row][col-1]&&s.L==j){
                        col--;
                        W(s);ok=true;
                    }else if(h[row][col]>h[row][col+1]&&s.R==j){
                        col++;
                        E(s);ok=true;
                    }
                }
            }while(ok);
            h[row][col]++;
            t[row][col]=s.U;
        }
        for(int i=1;i<=6;i++){
            int ret=0;
            for(int j=0;j<100;j++)
                for(int k=0;k<100;k++)if(t[j][k]==i)ret++;
            printf("%d",ret);
            if(i<6)printf(" ");
            else printf("\n");
        }
    }
}

2340
個数が一致していれば必ず作れる。

#include<stdio.h>
char str[2];
int main(){
    int a;
    scanf("%d",&a);
    long long v=0;
    for(int i=0;i<a;i++){
        int b,c;
        scanf("%d%s%d",&b,str,&c);
        if(str[0]=='(')v+=c;
        else v-=c;
        if(v==0)printf("Yes\n");
        else printf("No\n");
    }
}

2243
譜面の場所と足のcol座標2つと最後に使った足でDP

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char str[100001];
int v[100000];
int dp[100001][3][3][2];
int main(){
    while(1){
        scanf("%s",str);
        if(str[0]=='#')return 0;
        int len=strlen(str);
        if(len<=2){
            printf("0\n");
            continue;
        }
        for(int i=0;i<len;i++)v[i]=str[i]-'0';
        for(int i=0;i<=len;i++)
            for(int j=0;j<3;j++)
                for(int k=0;k<3;k++)
                    dp[i][j][k][0]=dp[i][j][k][1]=99999999;
        for(int i=0;i<3;i++)
            for(int j=i;j<3;j++)
                dp[0][i][j][0]=dp[0][i][j][1]=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<3;j++){
                for(int k=j;k<3;k++){
                    if((v[i]+2)%3<j){
                        dp[i+1][(v[i]+2)%3][k][0]=min(dp[i+1][(v[i]+2)%3][k][0],min(dp[i][j][k][0]+1,dp[i][j][k][1]));
                    }
                    else if((v[i]+2)%3>k){
                        dp[i+1][j][(v[i]+2)%3][1]=min(dp[i+1][j][(v[i]+2)%3][1],min(dp[i][j][k][0],dp[i][j][k][1]+1));
                    }else{
                        dp[i+1][(v[i]+2)%3][k][0]=min(dp[i+1][(v[i]+2)%3][k][0],min(dp[i][j][k][0]+1,dp[i][j][k][1]));
                        dp[i+1][j][(v[i]+2)%3][1]=min(dp[i+1][j][(v[i]+2)%3][1],min(dp[i][j][k][0],dp[i][j][k][1]+1));
                    }
                }
            }
        }
        int ret=9999999;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                ret=min(ret,min(dp[len][i][j][0],dp[len][i][j][1]));
        printf("%d\n",ret);
    }
}

2232
要はパネルでポン。面倒なシミュレーション。はぁ~。パネポンガチ勢だったので変なケース見つけられたのが幸いだが…

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[30][31];
char val[30][31];
bool kie[30][31];
int main(){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    for(int i=0;i<a;i++)scanf("%s",str[i]);
    for(int i=0;i<a;i++){
        for(int j=0;j<b-1;j++){
            if(str[i][j]=='.'&&str[i][j+1]=='.')continue;
            for(int k=0;k<a;k++)
                for(int l=0;l<b;l++){
                    val[k][l]=str[k][l];
                }
            char S=val[i][j];
            val[i][j]=val[i][j+1];
            val[i][j+1]=S;
            bool ok=true;
            //bool ze=true;
 
            for(int k=0;k<b;k++){
                int V=a-1;
                for(int l=a-1;l>=0;l--){
                    if(val[l][k]!='.')val[V--][k]=val[l][k];
                }
                for(int l=V;l>=0;l--)val[l][k]='.';
            }
            do{
                //ze=ok;
                for(int k=0;k<a;k++)
                    for(int l=0;l<b;l++)
                        kie[k][l]=false;
                ok=false;
                for(int k=0;k<a;k++){
                    char now=val[k][0];
                    int ren=val[k][0]!='.'?1:0;
                    for(int l=1;l<b;l++){
                        if(val[k][l]=='.'){
                            if(ren>=c){
                                for(int m=l-ren;m<l;m++)kie[k][m]=true;
                            }
                            now=val[k][l];
                            ren=0;
                        }else{
                            if(val[k][l]!=now){
                                now=val[k][l];
                                if(ren>=c){
                                    for(int m=l-ren;m<l;m++)kie[k][m]=true;
                                }
                                ren=1;
                            }else ren++;
                        }
                    }
                    if(ren>=c){
                        for(int m=b-ren;m<b;m++)kie[k][m]=true;
                    }
                }
                for(int k=0;k<b;k++){
                    char now=val[0][k];
                    int ren=val[0][k]!='.'?1:0;
                    for(int l=1;l<a;l++){
                        if(val[l][k]=='.'){
                            if(ren>=c){
                                for(int m=l-ren;m<l;m++)kie[m][k]=true;
                            }
                            now=val[l][k];
                            ren=0;
                        }else{
                            if(val[l][k]!=now){
                                now=val[l][k];
                                if(ren>=c){
                                    for(int m=l-ren;m<l;m++)kie[m][k]=true;
                                }
                                ren=1;
                            }else ren++;
                        }
                    }
                    if(ren>=c){
                        for(int m=a-ren;m<a;m++)kie[m][k]=true;
                    }
                }
                for(int k=0;k<a;k++)
                    for(int l=0;l<b;l++)
                        if(kie[k][l]){
                            val[k][l]='.';
                            ok=true;
                        }
                for(int k=0;k<b;k++){
                    int V=a-1;
                    for(int l=a-1;l>=0;l--){
                        if(val[l][k]!='.')val[V--][k]=val[l][k];
                    }
                    for(int l=V;l>=0;l--)val[l][k]='.';
                }
            //  for(int k=0;k<a;k++)
            //  printf("%s\n",val[k]);
            }while(ok);
            ok=true;
            for(int k=0;k<a;k++)
                for(int l=0;l<b;l++)
                    if(val[k][l]!='.')ok=false;
            if(ok){
                printf("YES\n");
                return 0;
            }
        }
    }
    printf("NO\n");
}

2175
変なルールがないので楽なシミュレーション

#include<stdio.h>
char str[13][4][3];
int num[13][4];
char pro[2];
int main(){
    while(1){
        scanf("%s",pro);
        if(pro[0]=='#')return 0;
        for(int i=0;i<4;i++)
            for(int j=0;j<13;j++)
                scanf("%s",str[j][i]);
        for(int i=0;i<13;i++)
            for(int j=0;j<4;j++){
                if(str[i][j][0]=='A')num[i][j]=14;
                else if(str[i][j][0]=='K')num[i][j]=13;
                else if(str[i][j][0]=='Q')num[i][j]=12;
                else if(str[i][j][0]=='J')num[i][j]=11;
                else if(str[i][j][0]=='T')num[i][j]=10;
                else num[i][j]=str[i][j][0]-'0';
                if(str[i][j][1]==pro[0])num[i][j]+=40;
            }
        int ns=0;
        int ew=0;
        int at=0;
        for(int i=0;i<13;i++){
            char c=str[i][at][1];
            int n=at;
            int p=num[i][at];
            for(int j=1;j<4;j++){
                if((c==str[i][(at+j)%4][1]||num[i][(at+j)%4]>40)){
                    if(p<num[i][(at+j)%4]){
                        p=num[i][(at+j)%4];
                        n=(at+j)%4;
                    }
                }
            }
            if(n%2)ew++;
            else ns++;
            at=n;
        }
        if(ew>6)printf("EW %d\n",ew-6);
        else printf("NS %d\n",ns-6);
    }
}

1316
全探索

#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;
char str[10][21];
int dx[]={1,1,1,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,-1,1,0,-1};
vector<string> V;
int main(){
    int a,b;
    while(scanf("%d%d",&a,&b),a){
        V.clear();
        for(int i=0;i<a;i++)scanf("%s",str[i]);
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                for(int k=0;k<8;k++){
                    int row=i;
                    int col=j;
                    string S="";
                    do{
                        S+=str[row][col];
                        row+=dx[k];
                        col+=dy[k];
                        if(row<0)row+=a;
                        if(row>=a)row-=a;
                        if(col<0)col+=b;
                        if(col>=b)col-=b;
                    }while(row!=i||col!=j);
                    V.push_back(S);
                }
            }
        }
        std::sort(V.begin(),V.end());
        int len=0;
        int m=0;
        for(int i=0;i<V.size()-1;i++){
            int P=0;
            for(int j=0;j<min(V[i].size(),V[i+1].size());j++){
                if(V[i][j]!=V[i+1][j])break;
                P++;
            }
            if(P>len){
                len=P;
                m=i;
            }
        }
        if(len<2)printf("0\n");
        else{
            for(int i=0;i<len;i++)printf("%c",V[m][i]);
            printf("\n");
        }
    }
}

難易度表250が埋まりました。
さすがに250はシミュレーションだらけでつまらないので、もっと高い点数も埋めていきます。