ABC 122
バイオインフォっぽかったがそんなことはなかった
A
- 相補塩基を表示する
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { char b; cin >> b; if (b == 'A') cout << 'T' << endl; if (b == 'C') cout << 'G' << endl; if (b == 'G') cout << 'C' << endl; if (b == 'T') cout << 'A' << endl; }
Submission #5129616 - AtCoder Beginner Contest 122
B
- 各位置からACGTだけで書ける部分列の長さを求めて、その最大値
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { string S; cin >> S; int ans = 0; REP(i, S.size()) { int cnt = 0; FOR(j, i, S.size()) { if (S[j] == 'A' || S[j] == 'C' || S[j] == 'G' || S[j] == 'T') cnt++; else break; } ans = max(ans, cnt); } cout << ans << endl; }
Submission #5129638 - AtCoder Beginner Contest 122
C
- 一番左から数えたときに
AC
がいくつあるかを持っておく l
番目とr
番目の差が答え
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int t[100001]; int main() { int N, Q; string S; cin >> N >> Q >> S; int cnt = 0; FOR(i, 1, N) { if (S[i - 1] == 'A' && S[i] == 'C') cnt++; t[i] = cnt; } REP(i, Q) { int l, r; cin >> l >> r; cout << t[r - 1] - t[l - 1] << endl; } }
Submission #5129691 - AtCoder Beginner Contest 122
D
- 自力では解けなかった
- 「ABCのDはDPのD」という格言通りDPで解く
- 最後の3文字を持っておいて、禁止文字列になる場合は遷移しないみたいな感じ(ここまでは分かったが正しく実装できなかった)
- 解説に従ってメモ化再帰で実装
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; vector<map<string, int>> memo(101); int N; const int MOD = 1e9 + 7; bool ok(string s) { if (s[0] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // A?GC if (s[0] == 'A' && s[1] == 'G' && s[3] == 'C') return false; // AG?C if (s[0] == 'A' && s[1] == 'G' && s[2] == 'C') return false; // AGC? if (s[1] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // ?AGC if (s[0] == 'G' && s[1] == 'A' && s[2] == 'C') return false; // GAC? if (s[1] == 'G' && s[2] == 'A' && s[3] == 'C') return false; // ?GAC if (s[0] == 'A' && s[1] == 'C' && s[2] == 'G') return false; // ACG? if (s[1] == 'A' && s[2] == 'C' && s[3] == 'G') return false; // ?ACG return true; } int dfs(int cur, string last3) { if (memo[cur].count(last3) == 1) { return memo[cur][last3]; } if (cur == N) return 1; int ret = 0; char bases[] = {'A', 'C', 'G', 'T'}; for (char c : bases) { if (ok(last3 + c)) { string s = last3.substr(1); s += c; ret = (ret + dfs(cur + 1, s)) % MOD; } } memo[cur][last3] = ret; return ret; } int main() { cin >> N; cout << dfs(0, "TTT") << endl; }
Submission #5130760 - AtCoder Beginner Contest 122
DPによる解法はAtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録が詳しい。