AtCoder Beginner Contest 122
はい。
https://atcoder.jp/contests/abc122
ooox 976(+45)でした。
復習でC++書いて追記しました。
A - Double Helix
#include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; if (s=="A") cout<<"T"<<endl; if (s=="T") cout<<"A"<<endl; if (s=="G") cout<<"C"<<endl; if (s=="C") cout<<"G"<<endl; return 0; }
Python3
d={"A":"T","T":"A","C":"G","G":"C"} print(d[input()])
全部連想配列で直書きしました。
B - ATCoder
#include<bits/stdc++.h> using namespace std; int main(){ int cnt=0,ans=0; char s[25]; scanf("%s",s); for (long i=0;i<strlen(s);i++) { if (s[i]=='A') cnt++; else if (s[i]=='C') cnt++; else if (s[i]=='G') cnt++; else if (s[i]=='T') cnt++; else cnt=0; ans=max(ans,cnt); } printf("%d\n",ans); return 0; }
Python3
d={"A","C","G","T"} ans=chk=0 s=input() for i in s: if i in d: chk+=1 ans=max(ans,chk) else: chk=0 print(ans)
A,C,G,Tのいずれかなら加算し続けました。
C - GeT AC
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sc2(a,b) scanf("%d %d",&a,&b) int w[100005]; char s[100005]; int main(){ int a,b,n,q,x; sc2(n,q); scanf("%s",s); for (int i=1;i<n;i++) w[i]=w[i-1]+((s[i-1]=='A' && s[i]=='C')-0) ; rep(i,q) { sc2(a,b); printf("%d\n",w[b-1]-w[a-1]); } return 0; }
Python3
n,q=map(int,input().split()) s=input() d=[0]*n for i in range(1,n): if s[i-1]=="A" and s[i]=="C": d[i]+=d[i-1]+1 else: d[i]=d[i-1] for i in range(q): l,r=map(int,input().split()) print(d[r-1]-d[l-1])
ACの出現回数をCの位置を基準にして累積和かな。
パラッと問題読んで最大105の長さの文字列を最大105回まっさらから調べるのは無理だから数えておくしかないだろうなー、とrまでの合計回数からl手前までの回数を引けば良さそうと思って適当に書いて手元で動作確認して良さそうだったので提出してAC。
C++で書いてて長さ100000の文字列の影響なのかstrlenが異様に遅かったので次回以降は気を付けます。
D - We Like AGC
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) #define sc1(a) scanf("%d",&a) int n,ans,mod=1e9+7; int dp[4][4][4][105]; int main(){ sc1(n); rep(i,4) rep(j,4) rep(k,4) { if (((i==0 && j==1 && k==2) || (i==0 && j==2 && k==1) || (i==1 && j==0 && k==2))!=true) { dp[i][j][k][3]=1; } //0:A 1:G 2:C 3:T } //AGC, GAC, ACG, A?GC, AG?C for (int i=3;i<101;i++) { rep(a,4) rep(b,4) rep(c,4){ if (b==0 && c==2) { dp[b][c][0][i+1] = (dp[b][c][0][i+1] + dp[a][b][c][i])%mod; dp[b][c][2][i+1] = (dp[b][c][2][i+1] + dp[a][b][c][i])%mod; dp[b][c][3][i+1] = (dp[b][c][3][i+1] + dp[a][b][c][i])%mod; } else if ((b==0 && c==1) || (b==1 && c==0) || (a==0 && c==1) || (a==0 && b==1)) { dp[b][c][0][i+1] = (dp[b][c][0][i+1] + dp[a][b][c][i])%mod; dp[b][c][1][i+1] = (dp[b][c][1][i+1] + dp[a][b][c][i])%mod; dp[b][c][3][i+1] = (dp[b][c][3][i+1] + dp[a][b][c][i])%mod; } else { rep(p,4) dp[b][c][p][i+1] = (dp[b][c][p][i+1] + dp[a][b][c][i])%mod; } } } int ans=0; rep(i,4) rep(j,4) rep(k,4) ans=(ans+dp[i][j][k][n])%mod; printf("%d\n",ans); return 0; }
写経です。参考先様は、
https://poporix.hatenablog.com/entry/2019/03/25/203820
DP配列の持ち方は、 DP[2文字前][1文字前][いま][長さi文字で末尾が~の個数]
という感じです、多分。
if分岐は末尾にGが使えない、Cが使えない、なんでも使えるで分けています。長さNで末尾3文字の全パターンの剰余を取った総和が解です、多分。