ゲノコン2021 ー DNA配列解析チャレンジ B - Practice 2

問題リンク

解説

LCS の DP と似ています。 LCS を知らないよって方は Educational DP Contest の F ~ J 問題の解説と類題集 - Qiita を読んでからやると理解が早いかもしれません。

(-, -) のペアは無駄

sim[-][-]  = -5 であるため、最後に -, - を続けるのは、 S _ {sop} を最大化する上では損です。

DP

ここで、動的計画法をします。

 dp _ {ij} := s i 文字使い、t j 文字使った時の  S _ {sop} の最大値

としましょう。

遷移が 3 通り考えられます。

(i, j) -> (i + 1, j + 1)

 si 文字目と  t j 文字目をペアにするとき、 sim[s[i]][t[j]] S _ {sop} に加算されます。よって、

 dp _{i + 1, j + 1} \leftarrow \max(dp _ {i + 1, j + 1}, dp _ {i, j} + sim[s[i]][t[j]])

となります。

(i, j) -> (i + 1, j)

 si 文字目と - をペアにするとき、 sim[s[i]][-] S _ {sop} に加算されます。このとき、 s だけ 1 文字進むことに注意すると、

 dp _{i + 1, j} \leftarrow \max(dp _ {i + 1, j}, dp _ {i, j} + sim[s[i]][-])

となります。

(i, j) -> (i, j + 1)

- t j 文字目をペアにするとき、 sim[-][t[j]] S _ {sop} に加算されます。このとき、 t だけ 1 文字進むことに注意すると、

 dp _{i, j + 1} \leftarrow \max(dp _ {i, j + 1}, dp _ {i, j} + sim[-][t[j]\)

となります。

これを  dp _ {0,0} から  dp _ {|s|, |t|} まで遷移させるといいです。

前述した通り、(-, -) のペアは損にしかならないため、 dp _ {|s|, |t|} S _ {sop} の最大値となります。

DP の復元

どこから遷移してきたかをメモすると楽だと思います。暇な時に書くかもしれません。

実装例

#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

void solve()
{
  const int sim[5][5] = { 
                    {1, -3, -3, -3, -5}, 
                    {-3, 1, -3, -3, -5},
                    {-3, -3, 1, -3, -5},
                    {-3, -3, -3, 1, -5},
                    {-5, -5, -5, -5, -5}
                  };
  std::string s, t; cin >> s >> t;
  std::vector<int> a(s.size()), b(t.size());
  for (int i = 0; i < (int)s.size(); ++i)
  {
    if(s[i] == 'A')
      a[i] = 0;
    else if(s[i] == 'C')
      a[i] = 1;
    else if(s[i] == 'G')
      a[i] = 2;
    else if(s[i] == 'T')
      a[i] = 3;
  }

  for (int i = 0; i < (int)t.size(); ++i)
  {
    if(t[i] == 'A')
      b[i] = 0;
    else if(t[i] == 'C')
      b[i] = 1;
    else if(t[i] == 'G')
      b[i] = 2;
    else if(t[i] == 'T')
      b[i] = 3;
  }

  std::vector dp(s.size() + 1, std::vector<int>(t.size() + 1, -inf));
  std::vector kkt89_cute(s.size() + 1, std::vector<std::pair<int, int>>(t.size() + 1, {-1, -1}));
  dp[0][0] = 0;
  for (int i = 0; i <= (int)a.size(); ++i)
  {
    for (int j = 0; j <= (int)b.size(); ++j)
    {
      if(i + 1 <= (int)a.size() and j + 1 <= (int)b.size())
      {
        if(chmax(dp[i + 1][j + 1], dp[i][j] + sim[a[i]][b[j]]))
        {
          kkt89_cute[i + 1][j + 1] = {i, j};
        }
      }
      if(i + 1 <= (int)a.size())
      {
        if(chmax(dp[i + 1][j], dp[i][j] + sim[a[i]][4]))
        {
          kkt89_cute[i + 1][j] = {i, j};
        }

      }
      if(j + 1 <= (int)b.size())
      {
        if(chmax(dp[i][j + 1], dp[i][j] + sim[4][b[j]]))
        {
          kkt89_cute[i][j + 1] = {i, j};
        }
      }
    }
  }

  std::pair<int, int> cur = {a.size(), b.size()};
  std::string resa, resb;
  while(cur.first + cur.second > 0)
  {
    const auto b = kkt89_cute[cur.first][cur.second];
    if(b.first + 1 == cur.first)
    {
      resa += s[b.first];
    }
    else
    {
      resa += '-';
    }
    if(b.second + 1 == cur.second)
    {
      resb += t[b.second];
    }
    else
    {
      resb += '-';
    }
    cur = b;
  }
  std::reverse(resa.begin(), resa.end());
  std::reverse(resb.begin(), resb.end());
  cout << resa << "\n";
  cout << resb << "\n";

}
int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int kkt = 1; 
  // cin >> kkt;
  while(kkt--)
    solve();
  return 0;
  
}