バイオインフォっぽかったがそんなことはなかった

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

B - ATCoder

各位置から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

C - GeT AC

一番左から数えたときに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

D - We Like AGC

自力では解けなかった
「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 点) - けんちょんの競プロ精進記録が詳しい。