AtCoder Beginner Contest 122(ABC122) 解説

青コーダーになるため、気合入れて埋めていきましょう。

A – Double Helix
B – ATCoder
C – GeT AC
D – We Like AGC

A – Double Helix

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

上手い書き方は色々あると思いますが、以下の対応表を実装するだけになります。

A -> T
C -> G
T -> A
G -> C

今回はif文でゴリゴリ書きました。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin>>s;
    
    if(s=="A") cout<<"T"<<endl;
    if(s=="C") cout<<"G"<<endl;
    if(s=="G") cout<<"C"<<endl;
    if(s=="T") cout<<"A"<<endl;
}

B – ATCoder

B - ATCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

Sの長さが最長10と短いので、全ての部分文字列に対して調べて最大を取ればOKです。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    cin>>s;
 
    int ans=0;
    for(int i=0;i<s.size();i++){
        for(int j=i;j<s.size();j++){
            bool f=true;
            for(int k=i;k<=j;k++){
                if(s[k]!='A'&&s[k]!='C'&&s[k]!='G'&&s[k]!='T') f=false;
            }
            if(f) ans=max(ans,j-i+1);
        }
    }
    cout<<ans<<endl;
}

C – GeT AC

C - GeT AC

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

単純に調べるとO(NQ)でTLEします。
区間の個数を求める問題ですが、この手の問題は累積和を使うと上手くハマります。

"AC"である個所を+1した配列に対して累積和をとる。
  ACACTACG
->01010010
->01122233
3 7区間を調べたい場合は、累積(7)-累積(3)=3-1=2とする。
※厳密には4 7区間の"AC"の数を調べていますが、"AC"のカウントの仕組み上。3 4で"AC"ができる場合、4で+1されているため問題ありません。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N,Q;
    cin>>N>>Q;

    string S;
    cin>>S;

    int c[N];
    c[0]=0;
    for(int i=1;i<N;i++){
        c[i]=c[i-1];
        if(S[i]=='C'&&S[i-1]=='A') c[i]++;
    }

    for(int i=0;i<Q;i++){
        int l,r;
        cin>>l>>r;
        cout<<c[r-1]-c[l-1]<<endl;
    }
}

D – We Like AGC

D - We Like AGC

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A, C, G, T 以外の文字を含まない。

だけを満たす場合、答えは単純に4^Nとなります。

AGC を部分文字列として含まない。
隣接する 2 文字の入れ替えを 1 回行うことで上記の条件に違反させることはできない。

入れ替えでAGCを作れてしまう状況を考えます。

3文字の場合
AGC
ACG (2,3文字目をチェンジ)
GAC (1,2文字目をチェンジ)
4文字の場合
AXGC (Xは任意の文字)
AGXC (Xは任意の文字)

の5パターンが考えられます。
今回、これらを含まないようにdpテーブルを更新することで解きました。
具体的には、

dp[見ている場所][3文字前][2文字前][1文字前]

とし、例えば3文字前=A,2文字前=T,1文字前=Gであるdpテーブルから更新する場合、次の文字として’C’は置けないため、そういったケースは除外するようにしました。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int N;
    int mod=1000000007;
    cin>>N;
    //XAGC XGAC XACG
    //AXGC AGXC
    int dp[101][4][4][4]={{{{0}}}};

    dp[0][3][3][3]=1;

    for(int i=1;i<=N;i++){
        for(int j=0;j<4;j++){
            for(int k=0;k<4;k++){
                for(int l=0;l<4;l++){
                    //0A 1C 2G 3T
                    dp[i][k][l][0]+=dp[i-1][j][k][l];
                    if((!(k==0&&l==2))&&(!(k==2&&l==0))&&(!(j==0&&l==2))&&(!(j==0&&k==2))) dp[i][k][l][1]+=dp[i-1][j][k][l];
                    if(!(k==0&&l==1)) dp[i][k][l][2]+=dp[i-1][j][k][l];
                    dp[i][k][l][3]+=dp[i-1][j][k][l];
                    dp[i][k][l][0]%=mod;
                    dp[i][k][l][1]%=mod;
                    dp[i][k][l][2]%=mod;
                    dp[i][k][l][3]%=mod;
                }
            }
        }
    }

    int ans=0;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(int l=0;l<4;l++){
                //cout<<i<<","<<j<<","<<l<<" "<<dp[N][i][j][l]<<endl;
                ans+=dp[N][i][j][l];
                ans%=mod;
            }
        }
    }

    cout<<ans<<endl;
}