ABC 122 反省会

今回出遅れもあってBまでしか解けなかった。今回からC++でやっていきたいという気持ちがある。

A: Double Helix

最初の回答。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
 char b;
 cin >> b;
 char p;
 if (b == 'A') {
   p = 'T';
 } else if (b == 'T') {
   p = 'A';
 } else if (b == 'C') {
   p = 'G';
 } else {
   p = 'C';
 }
 cout << p << endl;
}

辞書とかきっとあるよなと思って調べたらstd::mapがあったので次からスッと使えるようにしておきたい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<char, char> mp{
    {'A', 'T'},
    {'T', 'A'},
    {'C', 'G'},
    {'G', 'C'}
  };

  char b;
  cin >> b;
  cout << mp[b] << endl;
}

B: AT Coder

最初の回答。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string acgt = "ACGT";
  string s;
  cin >> s;
  int longest = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
      int start = i;
      int end = j;
      bool is_acgt = true;
      for (int k = start; k <= end; k++) {
        bool in_acgt = false;
        for (int l = 0; l < acgt.size(); l++) {
          if (s.at(k) == acgt.at(l)) in_acgt = true;
        }
        if (!in_acgt) is_acgt = false;
      }
      if (is_acgt && longest < (end - start + 1)) {
        longest = end - start + 1;
      }
    }
  }
  cout << longest << endl;
}

多少整理した。文字列の検索を覚えておきたい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string acgt = "ACGT";
  string s;
  cin >> s;
  int longest = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = i; j < s.size(); j++) {
      bool is_acgt = true;
      for (int k = i; k <= j; k++) {
        if (acgt.find(s.at(k)) == string::npos) {
          // 見つからないとstring::nposが返る
          is_acgt = false;
        }
      }
      if (is_acgt) {
        longest = max(longest, j - i + 1);
      }
    }
  }
  cout << longest << endl;
}

C: GeT AC

TLE連発の上ここで時間切れになった。そのまま考え続けて30分後くらいに解けた。出遅れが無かったらあるいは…

まだC++で試行錯誤しながら書くのに慣れていないのでこれはPythonで書いた。

# coding: utf-8
import sys
input = sys.stdin.readline

N, Q = [int(i) for i in input().split()]
S = input()
is_AC = [False] * N
AC_csum = [0] * N
for i in range(N):
  is_AC[i] = S[i:i+2] == "AC"
  AC_csum[i] = AC_csum[i-1] + is_AC[i]

for i in range(Q):
  l, r = [int(i) for i in input().split()]
  ans = AC_csum[r-1] - AC_csum[l-1] + is_AC[l-1] - is_AC[r-1]
  print(ans)

で、その後解説を見ながらC++で書いてみた。考え方は合っていたけど冗長なことをしていたっぽい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  
  vector<int> at_cnt(N + 1, 0);
  
  for (int i = 0; i < N; i++) {
    at_cnt.at(i + 1) = at_cnt.at(i) + (S.substr(i, 2) == "AC");
  }

  for (int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    cout << at_cnt.at(r - 1) - at_cnt.at(l - 1) << endl;
  }

D: We Like AGC

今回Dまでたどり着けてないのでこれはまた後で。

解説を見ながらC++で書いてみた。

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
vector<vector<int>> memo(200, vector<int>(200));
map<string, int> mp;
int mpidx = 0;

bool ok(string last4) {
  for (int i = 0; i < 4; i++) {
    string t = last4;
    if (i >= 1) {
      swap(t.at(i-1), t.at(i));
    }
    if (t.find("AGC") != string::npos) {
      return false;
    }
  }
  return true;
}

int dfs(int cur, string last3, int N) {
  if (mp.count(last3) == 0) {
    mp[last3] = mpidx;
    mpidx++;
  }
  if (memo.at(cur).at(mp[last3]) != 0) {
    return memo.at(cur).at(mp[last3]);
  }
  if (cur == N) {
    return 1;
  }
  int cnt = 0;
  for (int i = 0; i < 4; i++) {
    string acgt = "ACGT";
    char c = acgt.at(i);
    if (ok(last3 + c)) {
      cnt += dfs(cur + 1, last3.substr(1,2) + c, N);
      cnt %= MOD;
    }
  }
  memo.at(cur).at(mp[last3]) = cnt;
  return cnt;
}

int main() {
  int N;
  cin >> N;
  cout << dfs(0, "___", N) << endl;;
}