shortest_subsequence_1087.cpp (1853B)
1 #include <algorithm> 2 #include <array> 3 #include <iostream> 4 #include <ranges> 5 #include <string> 6 #include <vector> 7 8 // Idea: keep an array a[n][4] where a[i][x] denotes the shortest 9 // non-subsequence of s[:i] that ends with x. The recursive relation 10 // is the following: 11 // - For s[i] != x, a[i][x] = a[i-1][x] (easy to see). 12 // - For s[i] == x, we have a[i][x] = 1+min(a[i-1][y] over y): if 13 // the shortest non-subsequence ending with x becomes a subsequence, 14 // then this is realized by adding x to the any of the current 4 15 // non-subsequences (including the one already ending in x); otherwise, 16 // the subsequence obtained by removing the x is still a valid 17 // non-subsequence, and it must be one of the other 3, so we get back 18 // the same (it can't end again in x, otherwise it would be a shorter 19 // non-subsequence ending in x). 20 // Then we have to backtrack to find an actual solution. 21 22 size_t ind(char c) { 23 switch (c) { 24 case 'A': return 0; 25 case 'C': return 1; 26 case 'G': return 2; 27 case 'T': return 3; 28 default: return -1; 29 } 30 } 31 32 char dni(size_t i) { 33 static constexpr char a[] = {'A', 'C', 'G', 'T'}; 34 return a[i]; 35 } 36 37 size_t mi(const std::array<size_t, 4>& v) { 38 return *std::min_element(v.begin(), v.end()); 39 } 40 41 int main() { 42 std::string s; 43 std::cin >> s; 44 std::vector<std::array<size_t, 4>> a(s.size(), {1, 1, 1, 1}); 45 46 a[0][ind(s[0])] = 2; 47 for (size_t i = 1; i < s.size(); i++) 48 for (size_t j = 0; j < 4; j++) 49 a[i][j] = ind(s[i]) == j ? 1 + mi(a[i-1]) : a[i-1][j]; 50 51 auto l = s.size()+2; 52 std::vector<char> sol; 53 for (size_t i = s.size(); i > 0; i--) { 54 auto m = mi(a[i-1]); 55 if (l != m) { 56 l = m; 57 auto in = std::distance(a[i-1].begin(), 58 std::min_element(a[i-1].begin(), a[i-1].end())); 59 sol.push_back(dni(in)); 60 } 61 } 62 63 for (auto x : sol | std::views::reverse) 64 std::cout << x; 65 std::cout << "\n"; 66 }