第1回アルゴリズム検定

第一回 アルゴリズム実技検定

A - 2倍チェック

各文字数字であるかをチェックする．数字以外が一つでもあったらエラー．

int main() {
    string S;cin>>S;
    bool error=false;
    for(int i=0;i<3;i++){
        if(S[i]<'0'||'9'<S[i])error=true;
    }
    if(error){
        cout<<"error"<<endl;
    }else{
        cout<<stoi(S)*2<<endl;
    }
}

B - 増減管理

問題文の通りに実装するだけ．

int main(void){
    int N;cin>>N;
    vector<int>A(N);
    rep(i,N)cin>>A[i];
    rep(i,N-1){
        int d=abs(A[i]-A[i+1]);
        if(A[i]==A[i+1])cout<<"stay"<<endl;
        if(A[i]<A[i+1])cout<<"up "<<d<<endl;
        if(A[i]>A[i+1])cout<<"down "<<d<<endl;
    }
}

C - 3番目

ソートすれば楽．

int main(void){
    vector<int> A(6);
    rep(i,6)cin>>A[i];
    sort(all(A));
    cout<<A[3]<<endl;
}

D - 重複検査

添字に注意して実装する．

int main(void){
    int N;cin>>N;
    vector<int> A(N+1,0);
    bool c=true;
    int d=0;
    rep(i,N){
        int a;cin>>a;
        A[a]++;
        if(A[a]==2){
            d=a;
            c=false;
        }
    }
    int n=0;
    rep(i,N)if(A[i+1]==0)n=i+1;
    if(c){
        cout<<"Correct"<<endl;
    }else{
        cout<<d<<" "<<n<<endl;
    }
}

E - SNSのログ

問題文の通りに丁寧に実装する． コードが汚い．

int main(void){
    int N;cin>>N;
    int Q;cin>>Q;
    vector<vector<bool>> F(N,vector<bool>(N,false));
    rep(i,Q){
        vector<vector<bool>> F2(N,vector<bool>(N,false));
        int t;cin>>t;
        if(t==1){
            int a,b;cin>>a>>b;
            a--;b--;
            F2[a][b]=true;
        }else if(t==2){
            int a;cin>>a;a--;
            for(int k=0;k<N;k++){
                if(F[k][a]){
                    F2[a][k]=true;
                }
            }
        }else if(t==3){
            int a;cin>>a;a--;
            for(int k=0;k<N;k++){
                if(F[a][k]){
                    for(int l=0;l<N;l++){
                        if(F[k][l]&&l!=a){
                            F2[a][l]=true;
                        }
                    }
                }
            }
        }
        for(int i=0;i<N;i++){
            for(int k=0;k<N;k++){
                F[i][k]=F[i][k]||F2[i][k];
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int k=0;k<N;k++){
            cout<<(F[i][k]?"Y":"N");
        }
        cout<<endl;
    }
}

F - DoubleCamelCase Sort

問題文の通りに実装する．

int main(void){
    string S;cin>>S;
    vector<pair<string,string>> T(0);
    string tmp="";
    tmp.push_back(S[0]);
    for(int i=1;i<S.size();i++){
        tmp.push_back(S[i]);
        if('A'<=S[i]&&S[i]<='Z'){
            string tmp2="";
            for(char&c:tmp){
                if('A'<=c&&c<='Z')tmp2.push_back(c-'A'+'a');
                else tmp2.push_back(c);
            }
            T.push_back({tmp2,tmp});
            i++;
            tmp="";
            tmp.push_back(S[i]);
        }
    }
    sort(all(T));
    for(auto&t:T)cout<<t.second;
    cout<<endl;
}

G - 組分け

$3^10$があまり大きくないので，$3^10$通り全探索する．答えがマイナスになるパターンがあるので注意．

vector<vector<int>> permutation(int N,int U,bool h=false){
    //0,1,2,3,...,N-1のN個からU個選ぶ順列
    vector<vector<int>> A(0);
    auto fun = [&h,&A,&N,&U](auto &fun,vector<int> &B)->void{
        if((int)B.size()==U){
            auto C=B;
            do{
                A.push_back(C);
            }while(next_permutation(C.begin(),C.end()));
            return;
        }
        int s = (h?0:-1);
        if(!B.empty())s = B.back();
        for(int x=s+(h?0:1);x<N;x++){
            B.push_back(x);
            fun(fun,B);
            B.pop_back();
        }
    };
    vector<int> C={};
    fun(fun,C);
    return A;
}

int main(void){
    int N;cin>>N;
    vector<vector<long>> A(N,vector<long>(N));
    for(int b=0;b<N;b++){
        for(int a=b+1;a<N;a++){
            cin>>A[a][b];
        }
    }
    auto B = permutation(3,N,true);
    long ans = -INFl;
    for(auto &C:B){
        long s = 0;
        for(int b=0;b<N;b++){
            for(int a=b+1;a<N;a++){
                if(C[a]==C[b]){
                    s += A[a][b];
                }
            }
        }
        chmax(ans,s);
    }
    cout<<ans<<endl;
}

H - まとめ売り

全種類販売をするとき，1番カードの残りが少ないものよりも$a$が大きければ販売することができる． そうでなければ販売できない．よって，常に1番カードの残りが少ないものを記録しておけば良い．

int main(void){
    long N;cin>>N;
    vector<long>C(N);cin>>C;
    int Q;cin>>Q;
    long cnt = 0;
    long odd = 0,sum = 0;
    long minOdd = INFl,minEven = INFl;
    rep(i,N){
        if(i%2==1){//偶数
            chmin(minEven,C[i]);
        }else{
            chmin(minOdd,C[i]);
        }
    }
    rep(i,Q){
        int t;cin>>t;
        if(t==1){
            long x,a;cin>>x>>a;
            x--;
            if(x%2==0){//奇数
                if(C[x]-odd-sum-a>=0){
                    C[x]-=a;
                    cnt+=a;
                    chmin(minOdd,C[x]);
                }
            }else{
                if(C[x]-sum-a>=0){
                    C[x]-=a;
                    cnt+=a;
                    chmin(minEven,C[x]);
                }
            }
        }else if(t==2){
            long a;cin>>a;
            if(minOdd-odd-sum-a>=0){
                odd+=a;
                cnt+=a*((N+1)/2);
            }
        }else if(t==3){
            long a;cin>>a;
            if(minOdd-odd-sum-a>=0 && minEven-sum-a>=0){
                sum+=a;
                cnt+=a*N;
            }
        }
    }
    cout<<cnt<<endl;
}

I - 部品調達

bitDPの問題．

int main(void){
    int N,M;cin>>N>>M;
    vector<int> S(M,0);
    vector<long> C(M);
    rep(i,M){
        string s;cin>>s;
        for(auto&c:s){
            S[i]<<=1;
            S[i]|=(c=='Y');
        }
        cin>>C[i];
    }
    vector<vector<long>> dp(M+1,vector<long>(1<<N,INFl));
    //dp[a][b] := a番目まで集合bを得るコストの最小値
    dp[0][0] = 0;
    for(int a=0;a<M;a++){
        for(int b=0;b<(1<<N);b++){
            chmin(dp[a+1][b],dp[a][b]);
            chmin(dp[a+1][b|S[a]],dp[a][b]+C[a]);
        }
    }
    auto ans = dp[M][(1<<N)-1];
    if(ans==INFl)ans=-1;
    cout<<ans<<endl;
}

J - 地ならし

一見面倒な探索問題だが，$O((HW)^3)$でも間に合うことに甘えて愚直実装をする．

int main(void){
    int H,W;cin>>H>>W;
    vector<vector<long>>A(H+2,vector<long>(W+2,INFl));
    rep(i,H){
        rep(j,W){
            cin>>A[i+1][j+1];
        }
    }
    vector<vector<long>> BL(H+2,vector<long>(W+2,INFl));
    vector<vector<long>> BR(H+2,vector<long>(W+2,INFl));
    vector<vector<long>> UR(H+2,vector<long>(W+2,INFl));
    vector<int> dy={1,-1,0,0};
    vector<int> dx={0,0,1,-1};
    BL[H][1]=BR[H][W]=UR[1][W]=0;
    rep(_,H*W){
        rep1(i,H){
            rep1(j,W){
                rep(k,4){
                    chmin(BL[i][j],BL[i+dy[k]][j+dx[k]]+A[i][j]);
                    chmin(BR[i][j],BR[i+dy[k]][j+dx[k]]+A[i][j]);
                    chmin(UR[i][j],UR[i+dy[k]][j+dx[k]]+A[i][j]);
                }
            }
        }
    }
    long ans = INFl;
    rep1(i,H){
        rep1(j,W){
            chmin(ans,BL[i][j]+BR[i][j]+UR[i][j]-2*A[i][j]);
        }
    }
    cout<<ans<<endl;
}

K - 巨大企業